字符串匹配算法---BF及KMP
字符串匹配的一般算法（BF）
以 ABSABABCEF 与 ABCE 为例，求串2与串1匹配的第一个位置的下标（这里即输出 5），一般的，我们可以从串1的起始位置开始与串2比较，若相同则两串都向后移，否则，串1回到第二个位置，串2回到起始位置重新比较。
代码：（以hdu1771为例）
本题用此方法会超时
#include<stdio.h>
int a[10001],b[10001];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m,n;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int j=0;j<m;j++)
scanf("%d",&b[j]);
int k=0,s=0;
while(k<n&&s<m)
{
if(a[k]==b[s]){ //若相同，都向前进
k++;s++;
}
else{
k=k-s+1; //若不相同，串1回到k-s+1的位置，串2回到起始位置
s=0;
}
if(s==m){
printf("%d\n",k-s+1);
break;
}
}
if(s!=m)
printf("-1\n");
}
return 0;
}字符串匹配KMP算法
从上面一般算法中我们可以看到两字符串需要不断地回溯，这会导致复杂度增加，复杂度为O(M*N)，再M，N过大的情况下会超时，因此有了KMP算法。
图1
从上图中可以看出我们不必让串1回溯，串2也不必每次都回溯到起始位置，那么我们怎么判断让串2回溯到什么位置你呢？这里引入字符串前缀和后缀的最长匹配长度，用pmt数组保存，为了方便我们再使用Next数组。
图2.
如图一所示，比较至8的位置开始不相同，那么8之前的7个元素都是相同的，那么由前图2可知长度为7的字符串的前缀和后缀的最长匹配长度为3，所以我们可以知道串2只需要回退到pmt[7-1]的位置，即Next[7]的位置，所以我们用此方法来解决这道题。
AC代码（都以hdu1711为例）
#include<stdio.h>
int a[1000001],b[10001],Next[100001]; //求Next数组
void getNext(int m)
{
int i=0,j=-1;
Next[0]=-1;
while(i<m){
if(j==-1||b[i]==b[j]){
i++;j++;
Next[i]=j;
}
else
j=Next[j];
}
return ;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m,n;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int j=0;j<m;j++)
scanf("%d",&b[j]);
int k=0,s=0;
getNext(m);
while(k<n&&s<m)
{
if(a[k]==b[s]||s==-1){
k++;s++;
}
else{
s=Next[s];
}
if(s==m){
printf("%d\n",k-s+1);
break;
}
}
if(s!=m)
printf("-1\n");
}
return 0;
}