KMP算法我看了很多次，每次都觉得自己理解了，但是当返回头来用的时候，就又觉得不是很理解，今天我就把思路整理一下好了：
KMP算法主要有两个部分
1、计算next前缀函数，其实就是一个数组，每个元素储存了如果模式串和Target串在改点匹配不成功时，应该将模式串的那个点与之匹配。
2、实现模式串匹配
1、计算前缀函数：
该函数的基本思想是，找到某一点i前面（包含该点）前缀等于后缀的最大长度：举例：a b a a b a,其中设初始next[1] = 0,next[2]怎么算呢？包括下面几种情况，如果a[2]==a[1],那么next[2] = 1;如果a[2]!= a[1],证明前缀等于后缀的个数为0，那么next[2]=k=0；
next[3]呢?因为要找前缀和后缀，如果前面已经匹配了a[1],则匹配a[2],如果前面没有匹配a[1],那么就只能从头匹配a[1]，在此例中，因为next[2]=0,意味着a[2]未与T匹配，故继续从头匹配。因为a[3]==a[1],next[3]=k=1;
next[4]呢？正如前面所述，由于next[3]>0,故a[3]已经与T匹配了k个，则a[4]需要和a[k+1]进行匹配，即a[2],由于未匹配成功，故需要继续往前匹配,即a[1],匹配成功，则next[4] = k = 1;
next[5]呢？正如前面所述，由于next[4]>0,故a[4]已经与T匹配了k个，则a[5]需要和a[k+1]进行匹配，即a[2],由于匹配成功,则next[5] = k = 2;
next[6]呢？正如前面所述，由于next[5]>0,故a[5]已经与T匹配了k个，则a[6]需要和a[k+1]进行匹配，即a[3],由于匹配成功,则next[6] = k = 3;
伪代码如下：
next[1] = 0;//前缀数组
k = 0;//代表匹配的个数
for i=2:length
while k>0 && a[k+1] ！= a[i]
k = next[k];
if a[k+1] == a[i]
k = k + 1；
next[i] = k;
return next
2、KMP实现
m = T.length
n = P.length
next = 前缀函数返回值
k = 0;//匹配的个数
for i = 1: m // 每个元素进行匹配
while k > 0 && P[k + 1] != T[i]
k = next[k];
if P[k+1] == T[i]
k = k +１；
if k == m
return i-n
k = next[k]//将k移动至next[k]
end
原文链接：https://www.qiquanji.com/post/8422.html
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
微信扫码关注
更新实时通知