一、什么是KMP算法

KMP是发明这个算法三个人名字的第一个字母，没有特殊含义。

KMP用于在字符串A中找到字符串B是否出现，并找到出现的位置。

比如

字符串A[a,b,c,a,b,a,b,d,c]

字符串B[a,b,a,b,d]

可以在A中找到B，在A中出现的开始下标是3。

二、KMP算法好在哪

2.1 先看暴力算法差在哪

字符串A[a,b,a,d,a,b,a,b]

字符串B[a,b,a,b]

i是A的下标,j是B的下标。

第一趟比较

关注对比位置

A[a,b,a,d,a,b,a,b]

    |  |  |  |

B[a,b,a,b]

当第四次判断时候，i=3,j=3的时候,A[i]等于d,B[j] = b, 不相等，此时让i = 0+1，j=0，开启第二趟比较。

第二趟比较

A[a,b,a,d,a,b,a,b]

       | 

B   [a,b,a,b]

当第一次判断 ，i = 1，j=0的时候，A[i] != B[j], 第一位比较就不同，那么让i = 1+1,j=0，开启第三趟比较。

第三趟比较

A[a,b,a,d,a,b,a,b]

          |  | 

B      [a,b,a,b]

当第二次判断，i  = 3,j = 1的时候A[i] != B[j], 那么让i = 2+1,j=0，开启第四趟比较。

第四趟比较

A[a,b,a,d,a,b,a,b]

             |   

B         [a,b,a,b]

当第一次判断 ，i = 3，j=0的时候，A[i] != B[j], 第一位比较就不同，那么让i = 3+1,j=0，开启第五趟比较。

第五趟比较

A[a,b,a,d,a,b,a,b]

                |  |  |  |   

B            [a,b,a,b]

四次判断后，全部相同。

你会发现，每次比较失败，A要回退到这一次的起点的后一位。B要从0开始。

A的数据规模是n，B的数据规模是M，在最坏情况下，每次从 A 的一个新起点开始匹配 B所有元素，都可能比较接近 m 次，然后失败，再从下一个起点开始，如此反复，导致总比较次数在最坏情况下接近 n * m，时间复杂度为 O(n*m)。

最大的问题就在于，最坏情况下A的指针（或下标）会回退，每次移动A的指针后B的每个元素也都会和A中元素做比对。

2.2 KMP解决暴力算法的问题

一个直观的例子：

假设

字符串A为：A[0],A[1]...A[19],S  比如pfokbmhjuyAAAeratAAAS

字符串B为:   B[0],B[1]...B[9],Y  比如AAAeratAAAY

假设A[10...19] 与 B[0...9]相同，遍历到S和Y的时候发现S！=Y.

如果恰巧，B[0...2]与B[7...9]相同，那么必然有 A[10...12]和A[17...19]相同，例子中都是AAA

即B[0...2]、B[7...9]、A[10...12]和A[17...19]这四个都相同，当然B[0...2]和A[17...19]相同！

那么！我可以让A[20]这个S字母和B[3]对比来开启下一次匹配即可，所以让S在和Y比较失败后，让S直接与A[3]比较即可，因为B[0...2]和A[17...19]相同都是AAA。

那么到现在为止，问题就变成了，如果判定在判定失败的时刻，B的下标j之前的所有B[0...j-1]字母中，如何找到最长的真前缀和真后缀相等的字母数量。

理解上面这个简单的过程，就理解了kmp的关键，即要寻找最长真前缀=真后缀。

结果是什么，是在遍历A的过程中A的下标绝对不会回退，并且B的下标会向开头跳跃，但是也不是挨个回退，B 的下标 j 在整个匹配过程中只会「向右增加」或「跳到左边的小位置」，不会反复左右震荡。

整体 j 的增加次数 ≤ A 的长度 n
整体 j 的跳跃次数也 ≤ A 的长度 n

所以这一次遍历的时间复杂度是O(2n)即O(n)

到此为止可以理解思想了，下面是构建最长真前缀=真后缀的算法，即很多教程里面的在kmp算法中构建next数组或lps数组的过程。

三、寻找最长真前缀与真后缀相等的算法

记录当前最长相同前后缀长度是len，

让B的下标j=1，len=0，

当B[j] == B[len]说明有相同前后缀B[0]=B[1]，len++；j++,变成B[1]和B[2]的比较。

如果B[j] ！= B[len]，那就让len缩短但j不动，让B[0]和B[2]比较,如果B[0]==B[2]，那么说明B[0]!=B[1],B[1]!=B[2]，但是B[0]==B[2]，存在一位最长前后缀。直到len=0，让j++。

四、利用Lps数组记录从下标0开始到任意下标的字符形成的字符串，最长真前缀与真后缀相等的最长长度

我们快速走一遍

B = a b a b a c a

idx 0 1 2 3 4 5 6

初始化：

lps[0] = 0 len = 0 i = 1

i = 1, B[1] = 'b'

• B[1] != B[len=0] = 'a'

• len == 0 ⇒ lps[1] = 0，i = 2

i = 2, B[2] = 'a'

• B[2] == B[len=0] = 'a'

• len = 1

• lps[2] = 1

• i = 3

i = 3, B[3] = 'b'

• B[3] == B[len=1] = 'b'

• len = 2

• lps[3] = 2

• i = 4

i = 4, B[4] = 'a'

• B[4] == B[len=2] = 'a'

• len = 3

• lps[4] = 3

• i = 5

i = 5, B[5] = 'c'

• B[5] != B[len=3] = 'b'

• len > 0 ⇒ len = lps[2] = 1

• 再比较：B[5] != B[len=1] = 'b'

• len > 0 ⇒ len = lps[0] = 0

• len == 0 且 B[5] != B[0] ⇒ lps[5] = 0，i = 6

i = 6, B[6] = 'a'

• B[6] == B[len=0] = 'a'

• len = 1

• lps[6] = 1

• i = 7 结束

最终：

B =    a  b  a  b  a  c  a

idx     0  1  2  3  4  5  6

lps = [0, 0, 1, 2, 3, 0, 1]

那么假设当B的B[5]和A的字符相比不相等的时候，找到Lps[5-1] = 3,让B的下标跳转到3即可，即跳转到B[3] = b。此时A[i]前面的三个字符一定是aba。

五、为什么有人说kmp的时间复杂度是O(n+M)而不是O(n)

因为为B构造最长真前缀=真后缀的过程需要遍历一次B,遍历一次B是O(M)。

而在构造后成功后遍历一次A的时间复杂度是O(N)，在遍历A的过程中B只会向终点移动和向开头跳一次并且移动次数不大于A长度，跳跃次数也不大于A长度。

所以是O(N+M)。