KMP是用于字符串匹配的一种算法
emmmmm完全不知道怎么讲
理解了之后会发现思路挺好想的但是我用了一中午来理解
正常的字符串匹配都是一位一位枚举但在某些情况下复杂度太高
所以KMP算法应运而生
KMP是三个人的名字他们共同设计完成了这一算法【然而他们是谁www
这种算法在最坏情况下时间复杂度也为O(n);
那么KMP是怎么个思路呢
首先有一个文本串A一个子串B
要找到B在A中出现的位置
当我们从头枚举遇到不匹配的情况时本来应当从下一位再开始找
但是我们可以发现
像 A ACACBCABB
B ACAB
再次比对的时候不需要从第二位的C开始直接从第三位的A开始不是更方便吗
KMP的重点就在于在匹配过程中当匹配失败后从已匹配过的重复的字符串开始下一次比对
那么如何实现呢
啊啊啊好难讲想放弃嗷
放弃
我还是直接放代码吧orz
在注释里讲好了
完全不会讲啊【丧
我大概是假的理解了吧
#include#includeusing namespace std;#define maxn 1000010char l[maxn],s[maxn];int nxt[maxn];int main() {scanf("%s%s",l 1,s 1);//从第一位开始输int lenl strlen(l 1);int lens strlen(s 1);int k 0;//k记录当前字符能与某前缀匹配子串自己匹配自己nxt[1] 0;//第一个字符显然没有与之匹配的for(int i 2; i < lens; i) {//从第二位开始比对while(k s[k 1])//失配跳到之前匹配的地方k nxt[k];if(s[i] s[k 1])//匹配k;nxt[i] k;}k 0;//k记录匹配到第几位子串和文本串匹配for(int i 1; i < lenl; i) {while(k s[k 1])//失配跳到匹配的前缀处KMP算法精华所在k nxt[k];if(l[i] s[k 1])k;if(k lens)printf("%d\n",i - lens 1);}for(int i 1; i < lens; i)printf("%d ",nxt[i]);//题目要求orzreturn 0;}
【瘫
【我说的也太烂了吧喵的我讲什么了吗
【实名最水
三天之后觉得自己太丧于是准备再写写orz
emmmm
怎么说KMP算法自己匹配自己是精华所在也是比较不好理解的地方
尝试讲讲吧
一个字符串
abcabcd
当你从头开始比对匹配到第七位即d时失配了
这样你下一次开始匹配一定不是从第二位开始匹配
很明显我们可以看出第一到第三位与第四到第六位是一样的
我们下次匹配就从第四位开始
那么这样自己匹配自己就是看失配的位置的最长后缀能匹配到的前缀长度
emmm讲的乱七八糟orz
KMP真的挺不好理解的对于本蒟蒻来说
我用了一晚上加一中午理解到现在还讲不明白QAQ
希望大家能找到自己能看懂的题解学会KMP orz
转:https://www.cnblogs.com/sevenyuanluo/p/10065352.html