一对一匹配，KMP算法
Whiteying
2018-10-17 18:53:58
from:https://www.cnblogs.com/yjiyjige/p/3263858.html
模板：
```cpp
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=1e5; //字符串最大长度
string s,t; //s母串，t子串
int next[Maxn]; //不匹配时需要移动的位置
void findNext()
{
int k=-1;
int i=0;
memset(next,-1,sizeof(next));
while(i<t.length()-1)
{
if(k==-1||t[i]==t[k]) //有重复的字符时
{
if(t[++i]==t[++k]) // 当两个字符相等时要跳过
next[i]=next[k];
else
next[i]=k;
}
else
{
k=next[k];
}
}
}
int KMP()
{
int i=0,j=0;
while(i!=s.length()&&j!=t.length())
{
if(j==-1||s[i]==t[j]) //当j为-1时，要移动的是i，当然j也要归0
{
i++;
j++;
}
else
j=next[j]; //j回到指定位置
}
if(j==t.length()) //找到匹配的
return i-j;
else
return -1;
}
int main()
{
cin>>s>>t;
int tPos=KMP();
if(tPos==-1)
cout<<"Not has t!"<<endl;
else
cout<<"t is in "<<tPos<<"!"<<endl;
return 0;
}
/*
bacbababadababacambabacaddababacasdsd
ababaca
*/
```