poj 3461 && hdu 1686 Oulipo (kmp)
タイトルリンク:http://poj.org/problem?id=3461
問題解決レポート:文字列マッチングの鍵はnext配列が理解しにくいことです.
参考資料には
(1)next[0]=−1の意味:任意の列の最初の文字のモード値は−1とする.
(2)next[j]=-1の意味:パターン列Tにjと表記された文字が、先頭文字と
同じで、jの前の1-k文字と先頭の1-k文字
個の文字は等しくない(または等しいがT[k]==T[j])(1≦k例えば、T="abCabCad"ならnext[6]=-1、T[3]=T[6]
(3)next[j]=k意味:パターン列Tにjと表記された文字が、jの前にk個ある場合
文字は先頭のk文字と等しく、T[j]!=T[k] (1≤kすなわちT[0]T[1]T[2].T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
そしてT[j]!=T[k].(1≤k(4)next[j]=0の意味:(1)(2)(3)を除く場合.
next配列の意味:
1.next[n]= -1はA[m]とB[0]が間接的に比較したことを表して、等しくなくて、次の比較 A[m+1]とB[0]
2.next[n]=0は比較中に不等が生じたことを示し、次の比較 A［m］とB［0］.
3.next[n]=k>0しかしknext配列の求め方については、http://www.cppblog.com/oosky/archive/2006/07/06/9486.htmlを参照してください.
4.
問題解決レポート:文字列マッチングの鍵はnext配列が理解しにくいことです.
参考資料には
(1)next[0]=−1の意味:任意の列の最初の文字のモード値は−1とする.
(2)next[j]=-1の意味:パターン列Tにjと表記された文字が、先頭文字と
同じで、jの前の1-k文字と先頭の1-k文字
個の文字は等しくない(または等しいがT[k]==T[j])(1≦k
(3)next[j]=k意味:パターン列Tにjと表記された文字が、jの前にk個ある場合
文字は先頭のk文字と等しく、T[j]!=T[k] (1≤k
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
そしてT[j]!=T[k].(1≤k
next配列の意味:
1.next[n]= -1はA[m]とB[0]が間接的に比較したことを表して、等しくなくて、次の比較 A[m+1]とB[0]
2.next[n]=0は比較中に不等が生じたことを示し、次の比較 A［m］とB［0］.
3.next[n]=k>0しかしk
#include<cstdio>
#include<cstring>
using namespace std;
const int max1 = 10000 + 5;
const int max2 = 1000000 + 5;
int next[max1], len1, len2;
void get_next(char a[])
{
int i,j=-1;
memset(next,0,sizeof(next));
next[0]=-1;
for(i=1;i<=len1;i++)
{
while(j>-1&&a[j+1]!=a[i])
j=next[j];
if(a[j+1]==a[i])
j++;
next[i]=j;
}
}
int KMP(char a[],char b[])
{
get_next(a);
int i,j=-1,cnt=0;
for(i=0;i<len2;i++)
{
while(j!=-1&&a[j+1]!=b[i])
j=next[j];
if(a[j+1]==b[i])
j++;
if(j==len1-1)
cnt++;
}
return cnt;
}
int main()
{
char w[max1],t[max2];
int n,ans;
scanf( "%d",&n );
while( n-- )
{
len1=len2=0;
scanf("%s %s",w,t);
for(int i=0;w[i]!='\0';i++) len1++;
for(int j=0;t[j]!='\0';j++) len2++;
int ans = KMP(w,t);
printf("%d
",ans);
}
return 0;
} 4.