洛谷P3375:https://www.luogu.com.cn/problem/P3375
Knuth-Morris-Pratt字符串查找算法(简称为KMP算法)可在一个主文本字符串S内查找一个词W的出现位置。
KMP算法的作用是高效解决字符串匹配问题;
一般用暴力的方法解决字符串匹配问题是这样的
这个例子里我们可以看出第一次匹配失败第二次可以右移4位,而不是暴力算法的一位。也就是说这些步骤是没有意义的。我们想要优化就可以从这里入手。
我们可以判断出右移4位是因为前面的AB可以直接移到后面的AB处,这里就可以引进前缀后缀。仔细想一想,我们要移动的位数就是现在重合部分减去最长公共前后缀。
有了思想之后就要想怎么用代码实现了。
我们先要用nextt数组记录模板字符串从第一位到第i位的最长公共前后缀的长度。
如何记录呢,代码如下
重点注意i从2开始,nextt[1]=0。为什么呢,读者可以试一试从1开始然后输出nextt数组。
然后这段代码最重要的部分就是while那一行了。这也是比较难理解的地方。
每次匹配i和j+1.如果j+1不匹配,就跳到next[j]。第一次跳,匹配next[j]+1,再跳,就匹配next[next[j]] + 1.一直到j=0或者匹配成功。
此过程相当于模式串的自我匹配,所以不断的递归j = nextt[j],直到要么找到长度更短的相同前缀后缀,要么没有长度更短的相同前缀后缀
本人描述水平不佳,建议画图理解。
找到nextt数组后再进行比较。
while的过程和上面求nextt数组一样。
if(j==s2_l)是匹配的情况,后面可以进行一些操作,根据题目而定。此处是记录在文本字符串中匹配的位置。
其实我们可以发现这两个主要的过程差不多。
KMP算法就是对模板字符串自己进行一次匹配操作,然后再对文本字符串进行一次匹配操作。
完整代码如下
原文:https://www.cnblogs.com/xcsj/p/12215589.html