【算法】kmp

KMP算法

名称由来

是由发明这个算法的三个科学家的名称首字母组成

作用

用于字符串的匹配问题

举例说明

字符串 aabaabaaf
模式串 aabaaf

传统匹配方法

第一步

aabaabaaf
aabaaf

此时，b和f不一致，则把模式串从头和文本串的第二个字符开始比

第二步

aabaabaaf
_aabaaf

。。。。。以此类推，知道找到相同的或者结束

KMP算法

第一步

aabaabaaf
aabaaf

此时，b和f不一致，但是b和f前面的子串 aabaa
拥有最长相等前后缀2，因此可以跳过前两个字符 aa
，直接用文本串的 b 和 模式串的第三个字符继续比较

第二步

aabaabaaf
___aabaaf

。。。。。以此类推，知道找到相同的或者结束

最长相等前后缀

定义，以aabaa 为例
前缀：不包括最后一个字符
a
aa
aab
aaba

后缀：不包括第一个字符
a
aa
baa
abaa

最长相等前后缀就是 aa 长度为2

每一个字符串都对应一个最长相等前后缀表
aabaa
next[5] 0 1 0 1 2

如何求next表

初始化

next[0]=0

根据定义，单个字符，没有前后缀，最大公共长度自然为0

定义j=0,表示0…j为最长公共前后缀

定义i=1,从arr[1]开始遍历，求next[1]。。。

过程模拟

next[1]==next[0] 即next[i]==next[j]表示0…1(即0…i)子串aa的最大公共前后缀为0…0( 即0…j)a

j++

i++

next[2]!=next[1] 即next[i]!=next[j]表示0…1(即0…i)子串aa的最大公共前后缀为0…0( 即0…j)a