poj3461Oulipo
999 ワード
題意:簡単なKMP問題で、最初の文字列pが2番目の文字列sに現れる回数を探し出す.
構想:next配列を見つけてマッチングし、文字列pマッチングが完了するとカウンタに1を加算し、jはnext[j]に遡ってマッチングを継続する.
コード:
構想:next配列を見つけてマッチングし、文字列pマッチングが完了するとカウンタに1を加算し、jはnext[j]に遡ってマッチングを継続する.
コード:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
char p[10005],s[1000005];
int NEXT[10005];int sum,plen,slen;
void getnext ()// next
{
int i=0,j=-1;
NEXT[0]=-1;
while(i!=plen)
{
if(j==-1||p[i]==p[j])
{
i++;j++;
NEXT[i]=j;
}
else j=NEXT[j];
}
}
void kmp()//
{
int i=0,j=0;
getnext();
while(i!=slen&&j!=plen)
{
if(j==-1||s[i]==p[j])
{
i++;j++;
}
else j=NEXT[j];
if(j==plen)// ， sum=0， j next[j]
{
sum++;j=NEXT[j];
}
}
}
int main()
{
int t,i;
scanf("%d",&t);
for(i=0;i