我们将next数组计算出来以后,其余的就好说了,在匹配的时候,总的思想还是kmp数组的算法思想.
即便说到这,当时我还是死活看不懂,用手找个例子运行一下.
--------------------------------------------------------------------------------------------------------------------------------
总共提交了4次,通过这次我有点理解为什么zoj上的那道题不对了,不要用大数组作为函数的参数,虽然我现在讲不出理由,但直观的想想,即使传址来回跑多累,
#include<iostream>
#include<cstdio>
using namespace std;
int text[1000010];
int pattern[10010];
int n,m;
int next[10010];
void getnext()
{
int k=0;
next[0]=0;
int i;
for(i=1;i<m;i++)
{
while(k>0 && pattern[k] != pattern[i])
{
k=next[k-1];//k就是前缀后缀最长的数目
}
if(pattern[i]==pattern[k])
{
k++;
}
next[i]=k;
}
}
int kmp()
{
int i,q;
getnext();
q=0;
for(i=0;i<n;i++)
{
while(q>0 && pattern[q] != text[i])
q=next[q-1];
if(pattern[q] == text[i])
{
q++;
}
if(q == m)
{
return i-m+2;
break;
}
}
return -1;
}
int main()
{
// freopen("in.txt","r",stdin);
int i;
int kcase;
scanf("%d",&kcase);
while(kcase--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&text[i]);
for(i=0;i<m;i++)
scanf("%d",&pattern[i]);
if(n<m)
{
printf("-1\n");
continue;
}
getnext();
printf("%d\n",kmp());
}
}原文：http://blog.csdn.net/yuzibo747/article/details/20077831