KMP 算法的一种解释

[mightofcode]

KMP 算法很复杂，有很多解释方式（ DFA，前缀后缀），下面是我的一种理解。

我们在 s1 中匹配 s2，s1、s2 的长度分别为 N，M 1，首先我们按顺序匹配，直到匹配失败

i 表示 s1 的匹配起始位置，j 表示 s2 的匹配位置

2，如果使用暴力搜索算法下一步将是这样的：

这样算法的复杂度是N*M 但是我们可以利用已经匹配到的字符串（ AABAA ）进行优化：
3，由于 AABAA 是已知的与 s1 无关的信息，下一步我们可以做到匹配位置（红框）不变，i 向前跳过一些字符，j 变小，减少匹配长度
这种情况一共有以下几种：
可以看出来只有 C、D、E 是合法的（红框前面的部分必须匹配） 在 CDE 中我们只能选择 C，因为选择 D、E 会跳过 C 这个可能的正确匹配
4，这里的 C 其实就是 AABAA 的最长前缀后缀匹配
它满足：
1，C 是一个前缀后缀匹配：AABAA 的长度为 n 前缀和长度为 n 的后缀相等
2，C 是 n 最大的前缀后缀匹配
5，在 j=5 的时候，最长前缀后缀匹配的长度为 2
接下来要做的事情就是:
i+=(j-2)=3
j=2

而 i+j=5，所以当前匹配位置维持在红框处不变

6，所以只要我们计算出 s2 上面每个位置的最长前缀后缀匹配长度（前后缀匹配数组）就可以加速匹配过程了
更详细的分析可以看出 KMP 算法的匹配过程时间复杂度是 O(N)的

下面介绍如何计算前后缀匹配数组 preSuffixArr
1,首先 preSuffixArr[0]=0, 这是因为前后缀匹配不能匹配自己
2，然后 preSuffixArr[n]可以按照下面的规则递归计算：
首先取 v=preSuffixArr[n-1]，代表前 n-1 个字符的最长前后缀匹配：
如果 s2[v+1]==s2[n], 那么可以补上这个字符，构成一个长度为 n+1 的最长前后缀匹配
如果 s2[v+1]!=s2[n], 继续对 v=preSuffixArr[v-1]计算这个过程

下面示例介绍如何构造 AACAABAAA 的[前后缀匹配数组 preSuffixArr]

k 表示当前计算位置，
1，k=0,preSuffixArr[0]=0

2，k=1，然后由于 s2[0]==s2[1]="A",preSuffixArr[1]=preSuffixArr[0]+1

3，k=2，v=preSuffixArr[1]=1, 由于 s2[2]!=s2[1]，匹配失败 然后 v=preSuffixArr[v-1]=0, s2[2]!=s2[0], 匹配失败 preSuffixArr[2]=0

... 9，k=8，v=preSuffixArr[7]=2，s2[2]!=s2[8]，匹配失败

v=preSuffixArr[7]=2，s2[1]!==s2[8]，匹配成功

可以证明计算前后缀匹配数组的过程时间复杂度是 O(M)的，KMP 算法整体时间复杂度是 O(M+N)

不知道图为啥挂了
有兴趣的可以跳到 jianshu： https://www.jianshu.com/p/0f6b2e80eb51

[WuMingyu]

图挂了？当年上学还背过 KMP 算法，第二天就忘，现在就记得就是最大限度利用已知信息，还是那个通过 hash 匹配的算法好记

[xiexiping]

说实话，到现在都没完全搞明白这个算法

[mightofcode]

@xiexiping KMP 比较复杂，网上有很多解释，我想形成自己的一套理解能有助于理解 KMP 的本质

[lewis89]

@mightofcode #3 理解没用 关键是要理解那个后缀表达式 ，后缀表达式 匹配到多少个字符 然后就能往前多走几个空格，这样可以减少时间复杂度，从可理解可实现的方式来讲 KMP 远没有 RK 就是一楼说的 hash 的那种方式快，或者在实现层面上好理解。

[pipapa]

从状态机到 KMP 理解起来就很简单了

[Tubering]

每次看了不超过两天忘得一干二净，再看再忘。放弃挣扎了已经