Posted on 2009-08-29 05:06
Uriel 閱讀(477)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ 、
字符串處理
KMP變形。。匹配了一次之后不退出。。加上Next的值繼續(xù)比下去，直到串尾
/**//*Problem: 3461 User: Uriel
Memory: 1232K Time: 125MS
Language: C Result: Accepted*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int kmpMatch(char* Src, char* Pattern);
int GetNextdest(char* Pattern, int next[]);
int Next[10001];
int main()
{
char source[1000001];
char dest[10001];
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
memset(dest,0x00,sizeof(dest));
memset(source,0x00,sizeof(source));
scanf("%s",dest);
scanf("%s",source);
GetNextdest(dest,Next);
printf("%d\n",kmpMatch(source, dest));
}
return 0;
}
int kmpMatch(char* Src, char* Pattern)
{
int i=0,j=0;
int s_len,p_len;
int sum=0;
s_len=strlen(Src);
p_len=strlen(Pattern);
flag: while(i<s_len && j<p_len)
{
if(j==-1||Src[i]==Pattern[j])
{
++i;
++j;
}
else
{
j=Next[j];
}
}
if (j==p_len && i<s_len){sum++;j=Next[j];goto flag;}
else if(j==p_len && i==s_len){sum++;return sum;}
else
return sum;
}
int GetNextdest(char* Pattern, int next[])
{
int i=1,j=0;
int p_len=strlen(Pattern);
next[0]=-1;
while(i<p_len)
{
if(Pattern[i]==Pattern[j]||j==-1)
{
++i;++j;
if(Pattern[i]!=Pattern[j])next[i]=j;
else
next[i]= next[j];
}
else
j=next[j];
}
return 0;
}