今天碰见一个赤裸裸的 kmp 算法的题 直接找了个模板 但是却一直WA
后来 查自己的数据结构的书 改动一下
//if( pat[j] > 0) return -2;
//else return i-j;
return ((j==b)?(i-b) :-2);
后来就过了 郁闷 确实对于kmp 算法不是很熟啊
很是杯具
# include<stdio.h>
# include<string.h>
int fail[10000+1];
long a,b;
int kmp(int* str, int* pat){
int i, j, k;
memset(fail, -1, sizeof(fail));
//fail[0] = 0;
for (i = 1; i<b; ++i) {
for (k=fail[i-1]; k>=0 && pat[i]!=pat[k+1];k=fail[k]);
if (pat[k + 1] == pat[i]) fail[i] = k + 1;
//if(k == 0) fail[i] = k + 1;
}
i = j = 0;
while( i< a && j < b ){ // By Fandywang
if( pat[j] == str[i] ) ++i, ++j;
else if(j == 0)++i;//第一个字符匹配失败，从str下个字符开始
else j = fail[j-1]+1; }
//if( pat[j] > 0) return -2;
//else return i-j;
return ((j==b)?(i-b) :-2);
}
int src[1000000+1];
int dest[10000+1];
int main()
{
int T,i;
freopen("1284.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%ld%ld\n",&a,&b);
for(i = 0; i < a; i ++)
scanf("%d",&src[i]);
// src[i] = '\0';
for(i = 0; i < b; i ++)
scanf("%d",&dest[i]);
// dest[i] = '\0';
printf("%d\n",kmp(src,dest)+1);
}
return 0;
}
posted on 2010-07-26 19:42
付翔 阅读(601)
评论(2) 编辑 收藏 引用 所属分类:
ACM 数据结构