KMP算法的时间复杂度是如何计算的？

Question

假设在M字符串中找N字符串的起始位置，长度分别为m和n，使用KMP算法，一般认为时间复杂度是O（m+n），也就是计算next数组的时间复杂度是O(n)，而匹配的时候是O（m），但是在匹配的时候假设i用来标识M中的位置,j用来标识N中的位置，i是只增不减的可以理解，但是j也会按照next数组来回溯呀，也可能会回溯多次呀，为什么匹配的时候时间复杂度不是O(m*n)呢？求解

Answer 1

1. 计算Partial_Table(或者说是计算模式串的最长公共前缀后缀长度列表)时的比较次数介于[m,2m]，假设m时模式串的长度.
2. 比较模式串和子串时比较次数介于[n,2n],最坏情形形如T="aaaabaaaab",P="aaaaa".

所以算法时间复杂度时O(m+n).

Answer 2

j虽然回溯，但是向前进的

Answer 3

j的回溯只会影响搜索主循环次数的上下界（[m, 2m]），而不会像你说的使其变成m*n的关系。

你可以这样理解，由于m是只增不减的，所以最坏的情况是这样的：

1. 每次匹配都会失败（m保持不变）
2. 再次匹配也失败（m+1）

在这种情况下，对于M中的每个字符，实际上都比较了2次，所以一共执行了2m次循环。这是循环次数的上限。其他任何情况，都至少有若干次循环是m直接+1的。

Answer 4

当在 j 处失配时，j -> next[j] 是说回溯到位置 next[j]

注意，next[j] 的位置的含义是什么？是对齐了已经匹配好的串的位置。

下图中，红色的方格是失配处。一旦失配，j 发生回溯跳转，
因为新位置左边的串已经是匹配好的（这正是 next 数组的含义，前后公共缀的长度），所以无需回溯到头。

按上面的图，数一数，绿色的是匹配上的字符，红色的是失配的地方，横向 n 个，
纵向 m 个，总共 m + n 次比对。

每次失配，子串回溯，对齐已匹配串，在失配处原地再匹配一次主串对应字符

所以，kmp 的比对次数是(n + 失配次数）

KMP 算法的最差情况的一个案例，n/m 个失配点位，每个点位重新匹配 m-1 次，此时总共比对 n+(m-1)*(n/m) 次，接近 2n 次。

如果不考虑搜索到的情况，最好情况如下，总共比对 n+1*(n/m) 次，如果 m 很小，也接近 2n 次，如果 m 比较大，就接近 n 次。

算上预处理阶段，KMP 在最好、最坏的情况下的时间复杂度都是 O(m+n)

详细查看 https://writings.sh/post/algo...

Answer 5

KMP算法的一次比较只会产生两种结果，一种就是匹配成功主串的指针向前移动，一种是匹配失败模式串整体向前移动，两者都移动完时算法必然结束。前面的移动必为n次，后面的移动最多n次。所以最大的时间复杂度为2n，差异只存在于模式串移动的幅度