KMP算法学习链接：https://blog.csdn.net/starstar1992/article/details/54913261/
KMP算法：可以实现复杂度为O(m+n)
为何简化了时间复杂度：
充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量）。
上面理不理解无所谓，我说的其实也没有深刻剖析里面的内部原因。
充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量）。
上面理不理解无所谓，我说的其实也没有深刻剖析里面的内部原因。
考察目标字符串ptr：
ababaca
这里我们要计算一个长度为m的转移函数next。
ababaca
这里我们要计算一个长度为m的转移函数next。
next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。
比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。
cbcbc，最长前缀和最长后缀相同是cbc。
abcbc，最长前缀和最长后缀相同是不存在的。
cbcbc，最长前缀和最长后缀相同是cbc。
abcbc，最长前缀和最长后缀相同是不存在的。
**注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。
比如aaaa相同的最长前缀和最长后缀是aaa。**
对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是
a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和字符串下标相对应。
比如aaaa相同的最长前缀和最长后缀是aaa。**
对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是
a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和字符串下标相对应。
题目：Loj 103
题目描述
这是一道模板题。
给定一个字符串 AA 和一个字符串 BB，求 BB 在 AA 中的出现次数。AA 和 BB 中的字符均为英语大写字母或小写字母。
AA 中不同位置出现的 BB 可重叠。
输入格式
输入共两行，分别是字符串 AA 和字符串 BB。
输出格式
输出一个整数，表示 BB 在 AA 中的出现次数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
char str[maxn],mo[maxn];
int Next[maxn];
void getNext(){
Next[]=-;
int len=strlen(mo),k=-;
for(int i=;i<len;i++){
while(k>-&&mo[k+]!=mo[i])k=Next[k];
if(mo[k+]==mo[i])k++;
Next[i]=k;
}
}
int Kmp(){
getNext();
int len1=strlen(str),len2=strlen(mo),k=-,ans=;
for(int i=;i<len1;i++){
while(k>-&&mo[k+]!=str[i])k=Next[k];
if(mo[k+]==str[i])k++;
if(k==len2-){
k=Next[k]; //注意可重复，继续往前回溯
ans++;
}
}
return ans;
}
int main(){
scanf("%s %s",str,mo);
printf("%d\n",Kmp());
return ;
}
Loj 10043
题目链接：https://loj.ac/problem/10043
题目大意：
输入两个字符串A，B，计算B在A中出现的次数，两个子串之间不可重复。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
char str[],mo[];
int Next[];
void getNext(){
int len=strlen(mo),k=-;
Next[]=-;
for(int i=;i<len;i++){
while(k>-&&mo[k+]!=mo[i])k=Next[k];
if(mo[k+]==mo[i])k++;
Next[i]=k;
}
}
int Kmp(){
int len1=strlen(str),len2=strlen(mo),k=-,ans=;
getNext();
for(int i=;i<len1;i++){
while(k>-&&str[i]!=mo[k+])k=Next[k];
if(str[i]==mo[k+])k++;
if(k==len2-){
ans++;
k=-; //重新初始化，寻找下一个子串
}
}
return ans;
}
int main(){
while(~scanf("%s",str)){
if(strlen(str)==&&str[]=='#')break;
scanf("%s",mo);
printf("%d\n",Kmp());
}
return ;
}