poj 3461(KMP)

Oulipo
Time Limit:1000 MS
 
メモリLimit:65536 K
Total Submissions:17587
 
Acceepted:7059
Description
The Frech author Georges Perec(1936–1982)once wrote a book、La disparion、without the letter'.He was a member of the Oulipo group.A＿from the book:
Tout avait Pair normal,mas tout s’affirmart faux.Tout avait Fair normal,d’abobod,pusissurgissait l'inhumamaman,l'affolant.Il aurait voulu savoir o didis’ariculait mamamail'aaaaaaaaatrtrtrtraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaatrtrtrtrtrtrtrtrtrtrtrtrtrtrinininininininininininininininininstststststststststininininininun tabou,la vision d’un mal Oscur,d’un quot vacant,d’un non-dit:l avision,l’avision d’un oubl command tout,o zhous’abolissait lalison:tout avait l’air normal mas…
Perec would probably have scored high(or rather,low)in the follwing contest.People are asked to write a perhaps even meaningful text on some subject with as occurrences of a given"word"as"as possible.ject the.jurse.ject the.ject.in order to obtain a ranking of the comppetitors.The e comppetitors overy long texts with nonsense meaning;a sequence of 500,000 consecutive'T's is not unusual.And they never use spaces.
So we want to quickly find out how otens a word,i.e.a given string,occurs in a text.More formally:given the alphabet｛A',B',C',…,'Z''s and twonite streings strect strect.count the number of occurrences of W inT.All the consecutive characters of W must exactly match consecuve characters off.Occes may overlap.
Input
The first line of the input file contains a single number:the number of test cases to follow.Each test case has the follwing format:

One line with the word W,a string over{'A',B',C','Z',with 1≦|W≦10,000(here|W|124; Wthe length of the strigW).

One line with the text T,a string over{'A'、'B'、'C',…,'Z',with_;≦𞓜T|≦1,000,000.

Output
For evry test case in the input file,the output shout shout contain a single number,on a single line:the number of occurrences of the wodW in the text T.
Sample Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output

1
3
0

ソurce
BAPC 2006 Qualfication
 
本題はたくさん話しましたが、メインストリングの出現回数が要求されます.
KMPアルゴリズムを使って、もう一度マッチングしたら終了しません.スライドモードの列は次のマッチを開始します.全体の効率はいいです.
 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

char W[10010],T[1000010];//W    ，T   
int next[10010];

//KMP     next[]  
void getNext(char *p)
{
    int j,k,len=strlen(p);
    j=0;
    k=-1;
    next[0]=-1;
    while(j<len)
    {
        if(k==-1||p[j]==p[k])
        {
            next[++j]=++k;
        }
        else k=next[k];
    }
}

//KMP       W   T      
int KMP_count(char *W,char *T)
{
    int i,wlen=strlen(W),tlen=strlen(T),j=0,ans=0;
    getNext(W);
    for(i=0;i<tlen;i++)
    {
        while(j>0&&T[i]!=W[j])
          j=next[j];
        if(W[j]==T[i])j++;
        if(j==wlen)
        {
            ans++;
            j=next[j];
        }
    }
    return ans;
}

int main()
{
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        scanf("%s%s",&W,&T);
        strlen(W);
        strlen(T);
        printf("%d
",KMP_count(W,T));
    }
    return 0;
}