今天碰見一個赤裸裸的 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
付翔 閱讀(627)
評論(2) 編輯 收藏 引用 所屬分類:
ACM 數據結構