为什么我们要学习KMP呢？这就不得不说起当年暑假在校队集训的时候，苦逼做不出题目的痛苦时光了。
三个人看着题目中字符串匹配的那个环节，思索了整整三个小时。
不得不说，从0到1，远比在前人的肩膀上前行要难得多。真不知的这些变态大佬是怎么想出来的。
先来提及一下，当时我们用人脑想出来的代码(我没有说他们不是人：对于大部分人来说，那肯定就是一个个照着去比对就行了，然而很遗憾的是：
可惜时间太短，我无法爱上你——超时......
这就是那所谓的BP算法
1.朴素模式匹配（BP）
由于这个真的太基础，懒得废话了。就是应该去主串和模式串一个个去配对，如果该字符匹配，则j++，否则j=0，然后i++
int index_BP(string s,string p){
int sl=s.length(),pl=p.length();
for(int i=0;i<=sl-pl;i++){
int flag=1;
for(int j=0;j<pl;j++){
if(s[i+j]=!p[j]){
flag=0;
break;
}
}
if(flag)
return i;
}
return -1;
}2.KMP算法（三个人名...）
（1）前缀与后缀
什么是前缀和后缀捏？
ju个栗子，比如说有个字符串“abac”，那么对于该字符串而言，“a”，“ab”，“aba”则是它的前缀(PS:严格来讲，“abac”和空串也可以算作前缀)。
相应的，对于后缀而言就是，“c”，“ac”，“bac”等。
（2）next数组
这个时候，可能就会想前后缀和字符串的匹配有什么关系呢？其实，重点就在于信息的重复利用。
比如说，对于模式串“abdad”而言，如果在第5个字符“d”的时候不匹配，那么我们不需要再次去重头可以匹配，因为对于字符串“abda”而言，有相同的前后缀“a”。
所以我们只需要从“b”开始进行相应的配对即可。
从这里就可以看出，KMP算法实质就是利用当前字符前的字符子串的相同前后缀，来跳过大量没有意义的重复匹配。
这个是相关的动画。。。有点丑，而且有点慢，但是，菜狗的我不会调速度
接下来就是求next数组了，next数组是利用模式串得到的。
那为什么要叫做next数组呢？那是因为如果当前字符不匹配，下一个要比对的模式串的字符是哪个。
相应的计算公式如上所示。
（3）相关的代码
int mynext[200000];
void get_next(string s){
int l=s.size(),k=-1;
mynext[0]=-1;
for(int i=1;i<=l;){
if(k==-1||s[i]==s[k]){
i++;k++;
mynext[i]=k;
}
else k=mynext[k];
}
}
int index_kmp(string s,string p,int pos){
int i=pos,j=0;
int sl=s.size(),pl=p.size();
for(i=pos,j=0;i<sl&&j<pl;){
if(j==-1||s[i]==p[j]){
i++;j++;
}
else j=mynext[j];
}
if(j>=pl) return i-pl;
else return -1;
}3.相关例题
P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)文章来源：https://www.toymoban.com/news/detail-843661.html
Password - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)文章来源地址https://www.toymoban.com/news/detail-843661.html
到了这里，关于菜狗的KMP学习的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
