大二的时候百度看不懂，现在大三下学期了百度也看不懂。（实在是不能理解这个next数组究竟是怎么样工作的，为什么会得出那样的结果。）如果有好心人知道的话希望可以联系我告诉我（邮箱：4609019410@qq.com）
作用：字符串匹配
我们设匹配串为t，待匹配串为s，这个算法的功能就是在指定s中，从s的第i位字符开始搜索，判断在s中是否有t存在。
如果有则返回出现了t的首位字符位置（当然，这个数组是从0开始），如果没有则返回0。
通过next数组对匹配串t进行一个预处理，我们获得一个next数组。
下面的描述：string t：从0开始，next[]：从1开始
i=1;
这个next数组的意义是：对于我们要处理的字符串t里的第(i-1)字符对应的每一个next[i]元素
next[i]保存的是：从t[0]开始到t[i-1]的这一段字符串所有前缀与后缀的最大匹配长度。
next在kmp算法里发挥的作用：在每一次的匹配中，当碰上失配的情况（我们设初始态：t[0]与s[pos]开始比较，如果相等则两个指针同步增加变量。假设加到j时失配，即s[pos+j]!=t[j]）
我们可以利用next数组存储的信息，让它加速前进（而不是像朴素的模式匹配算法那样一位一位地挪，又从t[0]开始与s[pos]，提高匹配效率。）
几番周折还是弄不懂究竟是怎么运作的，所有只好先把实现的放上来，以后在琢磨是怎么回事了。以后弄明白了再回来说。。
#include<iostream>
#include<cstring>
using namespace std;
void get_next(string t,int *next)
{
int i=1,j=0;
next[1]=0;
while(i<t.length())
{
if(j==0||t[i]==t[j])
{
i++;j++;
next[i]=j;
}
else j=next[j];
}
}
int index_KMP(string s,string t,int pos)
{
int i=pos-1;
int j=0;
int next[255];
get_next(t,next);
//for(int i=1;i<=t.length();i++){
//cout<<next[i]<<" ";
//}
//cout<<endl;
while(i<s.length()&&j<t.length())
{
if(j==0||s[i]==t[j])
{i++;j++;}
else j=next[j];
}
if(j>=t.length())
return i-t.length();
else return 0;
}
int main()
{
string a,b;
cin>>a>>b;
int w;
cin>>w;
int ans=index_KMP(a,b,w);
cout<<ans<<endl;
return 0;
}