知识点
KMP算法简介
KMP算法由三位大佬Knuth，Morris，Pratt创造出来。
KMP算法是用来在主串中计算模式串出现的次数。
其核心思想是创建一个next表，然后再用主串与模式串匹配，如果失配，则通过next表跳过不可能匹配成功的位置，找的新位置进行匹配。
时间复杂度O(n+m),其中n为主字符串的长度，m为模式字符串的长度。
border及求next数组
border
一个字符串的border是指一个既是原串的严格前缀也是原串的严格后缀的字串的长度。
如：
ababccdgfabab的border是abab
next数组
next数组是KMP算法的核心，里面存的就是字符串每个前缀的border。
abcabc的next[4]=2,而s[next[4]+1]=s[5]=“c”,next[5]=3
我们可以得出,如果当前字符等于next[i-1]对应字符串往后的一个字符，则每个字符串的next[i]=next[i-1]+1;
否则继续往后跳（j=next[j]）;
代码：
int i,j,ans=0;
for(Next[1]=j=0,i=2;s[i];i++){
while(j&&s[i]!=s[j+1]){
j=Next[j];
}
if(s[i]==s[j+1]){
j++;
}
Next[i]=j;
}
补充：字符串s最小循环节长度=s.size()-border(s)
KMP算法过程
先求出next数组。
然后遍历主串匹配，失配则从j（失配位置）跳到next[j+1],还不相等，继续后跳。
否则j++,准备接着匹配。
如果遍历完模式串，从next[j]重新匹配
代码：
s=" "+s;
a=" "+a;
int i,j,ans=0;
for(Next[1]=j=0,i=2;s[i];i++){
while(j&&s[i]!=s[j+1]){
j=Next[j];
}
if(s[i]==s[j+1]){
j++;
}
Next[i]=j;
}
for(int i=1,j=0;a[i];i++){
while(j&&a[i]!=s[j+1]){
j=Next[j];
}
if(a[i]==s[j+1]){
j++;
}
if(!s[j+1]){
j=Next[j];
ans++;
i+=s.size()-2;
}
}
例题
题目：剪布条
题目描述
多组输入，输入“#”结束。
每次输入一个主串a和模式串s,求从a中能截出多少个s;
输入样例
abcde a3
aaaaaa aa
#
输出样例
0
3
剪布条题解
思路
直接进行KMP函数，不过要注意，遍历完模式串i要变到匹配成功部分的前一个位置，保证一部分不重复被截。
代码
#include<iostream>
#include<string>
using namespace std;
string s,a;
int Next[1000005];
void solve(string a,string s){
s=" "+s;
a=" "+a;
int i,j,ans=0;
for(Next[1]=j=0,i=2;s[i];i++){
while(j&&s[i]!=s[j+1]){
j=Next[j];
}
if(s[i]==s[j+1]){
j++;
}
Next[i]=j;
}
for(int i=1,j=0;a[i];i++){
while(j&&a[i]!=s[j+1]){
j=Next[j];
}
if(a[i]==s[j+1]){
j++;
}
if(!s[j+1]){
j=Next[j];
ans++;
i+=s.size()-2;
}
}
cout<<ans<<"\n";
}
int main(){
string s1,s2;
while(1){
cin>>s1;
if(s1=="#"){
break;
}
else{
cin>>s2;
solve(s1,s2);
}
}
return 0;
}
