很有启发的几篇文章：
文章传送门：
文章一：KMP算法的Next数组详解
文章二：从头到尾彻底理解KMP
文章三：字符串匹配的KMP算法
首先说说字符串模式匹配问题：
问题描述：子串的定位操作通常称作串的模式匹配，即查找子串在主串中的位置。我们把主串称为S，子串称作模式串T，用 i 和 j 指示主串S和模式串T中当前正待比较的字符位置。
算法基本思想：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较下个字符(pos值不变)；若不相等,从主串的pos++个字符起再重新和模式串的第一个字符比较。依次类推，直到模式串T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数值为主串里的匹配串第一个字符在主串中的序号，若匹配不成功，函数值返回0.
上图：
匹配过程如下：
1：pos=1,i=1;j=1;S[i]==T[j],继续比较到i=6,j=6时S[6]!=T[6]
2：pos=2,i=2;j=1;S[i]!=T[j]
3：pos=3,i=3;j=1;S[i]!=T[j]
4：pos=4,i=4;j=1;S[i]==T[j],i=5;j=2;S[i]==T[j]一直到i=9;j=6时匹配成功，函数值为4.
数据结构描述：
//求子串位置的定位函数 Index(S,T,pos)
int Index(SString S,SString T,int pos){
//返回子串T在主串中第pos个字符之后的位置。若不存在，则函数值为0.
//其中，T非空，1<=pos<=StrLength(S)
i=pos;j=1;
while(i<=S[0]&&j<=T[0]){
if(S[i]==T[j]){//继续比较后续字符
i++;
j++;
}
else{//指针后退重新开始匹配
i=i-j+2;
j=1;
}
}
if(j>T[0])return i-T[0];
else return 0;
}//Index
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string S,T;//S是主串，T为模式串
cin>>S>>T;
int pos=0,flag=0,ans=-1;//flag==1，则匹配成功
while(1){
int i=pos;//i是主串的位置指针
if(S.size()-i<T.size()){
break;
}
for(int j=0;j<T.size();j++){//j是模式串的位置指针
if(S[i]==T[j]){
i++;
if(j==T.size()-1){
flag=1;
ans=pos+1;//S下标是从零开始，故ans在pos基础上加1
break;
}
continue;
}
else{
pos++;
break;
}
}
if(flag==1){
break;
}
}
cout<<ans<<endl;
return 0;
}
KMP算法介绍：
这个算法是由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终由三人于1977年联合发表。这种算法被称为 Knuth-Morris-Pratt 操作，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置。
上图：
kmp过程
1：i=1;j=1.继续逐一比较直到i=6;j=6时S[i]!=L[j]
2：i=4;j=1.继续逐一比较直到i=9;j=6匹配成功
显然，KMP算法改进之处在于，每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右”滑动“尽可能远的一段距离后继续进行比较。那么问题来了，模式串向右“滑动”的可行距离多远，即当主串中第 i 个字符与模式中第 j 个字符比较不等时，主串中第 i 个字符应与模式串中哪个字符进行比较？（注意, i 不回溯。）
由此引出数组:
令;则
表明当模式串中第
个字符与主串第
个字符“失配”时，在模式串中需重新和主串中该字符进行比较的字符的位置。即
就是模式串向右“滑动”的距离。所以问题在于如何求
数组？
引出前缀和后缀：假设主串''，模式串为'
'，并假设此时应与模式串中第
个字符继续比较，则模式串中前
个字符的子串必须满足关系式
,且不可能存在
满足下列关系式
''='
'
已经得到的“部分匹配”的结果是
''='
'
由式和式
推得下列等式
''='
'
式子用文字描述：
模式串中存在两个相同的子串，该子串以模式串的第一个字符为首字符，长度为，
就是"前缀"和"后缀"的最长的共有元素的长度。"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
举例：
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[C,BC]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[D,CD,BCD]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，
后缀为[A,DA,CDA,BCDA]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为 [B,AB,DAB,CDAB,BCDAB]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[D,BD,ABD,DABD,CDABD,BCDABD]，共有元素的长度为0。
求数组的代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int nxt[maxn];
void getNext(string p){
// 初始条件
int j=0;
int k=-1;
nxt[0]=-1;
// 根据已知的前j位推测第j+1位
while(j<p.size()-1){//p[k]表示前缀，p[j]表示后缀
if(k==-1||p[j]==p[k])nxt[++j]=++k;
else k=nxt[k];
}
}
int main(){
string p;
cin>>p;
getNext(p);
for(int i=0;i<p.size();i++)
cout<<nxt[i]<<' ';
cout<<endl;
return 0;
}
运行：
改进：
void getNext(string p){
// 初始条件
int j=0;
int k=-1;
nxt[0]=-1;
// 根据已知的前j位推测第j+1位
while(j<p.size()-1){//p[k]表示前缀，p[j]表示后缀
if(k==-1||p[j]==p[k]){
++j;
++k;
if(p[j]!=p[k])nxt[j]=k;//优化
else nxt[j]=k;
}
else k=nxt[k];
}
}
改进原因：当p[j] != s[i] 时，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]咋办呢？答案是需要再次递归，即令next[j] = next[ next[j] ]。
如图：
!=
注意
==
若不优化，此时应该找到nxt[j],此时j==3，
因此此nxt[3]==1;而p[nxt[3]]==b;是无效操作。
完整版算法
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int nxt[maxn];
string s,p;
void getNext(string p){
// 初始条件
int j=0;
int k=-1;
nxt[0]=-1;
// 根据已知的前j位推测第j+1位
while(j<p.size()-1){//p[k]表示前缀，p[j]表示后缀
if(k==-1||p[j]==p[k]){
++j;
++k;
if(p[j]!=p[k])nxt[j]=k;//优化
else nxt[j]=k;
}
else k=nxt[k];
}
}
int kmp(int lens,int lenp){
int i=0,j=0,ans=-1;//如果最后ans==1,则匹配失败
while(i<lens&&j<lenp){
if(j==-1||s[i]==p[j]){
i++;
j++;
}
else j=nxt[j];
if(j==lenp)return ans=i-lenp+1;//习惯上第一个字符下标为1
}
return ans;
}
int main(){
//string s,p;
cin>>s>>p;
memset(nxt,-1,sizeof(nxt));
getNext(p);
int lens=s.size();
int lenp=p.size();
int ans=kmp(lens,lenp);
cout<<ans<<endl;
return 0;
}
