对题面的疑问

原题链接： https://ac.nowcoder.com/acm/problem/206 通配符匹配

先说疑问：我认为本题并不存在时间复杂度O(n)且空间复杂度O(1)的解法。

虽然本题的题面里写着进阶做法是时间复杂度O(n)且空间复杂度O(1)，但是所有题解均采用了二维dp或者双指针的做法，而这两种做法的时间复杂度全部都为O(n * m)。

部分题解将双指针做法的时间复杂度误说成了O(n)。

以下是极端样例下该题解代码的一次运行时间测试：

s: aaaaaa.......b（长度30000左右）

p: *aaaaa.......c（长度30000左右）

运行时间大约为5492ms。

同样的，s和p的构造方式不变，仅字符串长度均改为大约10000和100000时的测试结果如下：

可以发现运行时间大致相差了100倍，可以证明解法的严格时间复杂度为O(n * m)。

作为对比，[CQOI2014] 通配符匹配在本题的基础上，增加了"通配符个数不超过10个"的限制条件，才有了按照通配符给字符串分段后跑字符串哈希的时间复杂度O(n)做法。（将通配符影响的时间复杂度视作常数）

原题链接：https://ac.nowcoder.com/acm/problem/19935 [CQOI2014] 通配符匹配

因此对于开头的题目是否真的存在时间复杂度O(n)，空间复杂度O(1)的写法表示疑问，如有误望指正