1598: 最长公共前缀

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 109  Solved: 92

[][][]

Description

给定两个字符串s和t，现有一个扫描器，从s的最左边开始向右扫描，每次扫描到一个t就把这一段删除，输出能发现t的个数。

Input

第一行包含一个整数T（T<=50），表示数据组数。

每组数据第一行包含一个字符串s，第二行一个字符串t，字符串长度不超过1000000。

Output

对于每组数据，输出答案。

Sample Input

2abababababababba

Sample Output

32

HINT

Source

 

放一个KMP算法模板吧。。还没怎么做过KMP的题.

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N = 1000002;int Next[N];char S[N], T[N];int slen, tlen;void getNext(){    int j, k;    j = 0; k = -1; Next[0] = -1;    while(j < tlen)        if(k == -1 || T[j] == T[k])            Next[++j] = ++k;        else            k = Next[k];}/*返回模式串T在主串S中首次出现的位置返回的位置是从0开始的。*/int KMP_Index(){    int i = 0, j = 0;    getNext();    while(i < slen && j < tlen)    {        if(j == -1 || S[i] == T[j])        {            i++; j++;        }        else            j = Next[j];    }    if(j == tlen)        return i - tlen;    else        return -1;}/*返回模式串在主串S中出现的次数*/int KMP_Count(){    int ans = 0;    int i, j = 0;    if(slen == 1 && tlen == 1)    {        if(S[0] == T[0])            return 1;        else            return 0;    }    getNext();    for(i = 0; i < slen; i++)    {        while(j > 0 && S[i] != T[j])            j = Next[j];        if(S[i] == T[j])            j++;        if(j == tlen)        {            ans++;            j = Next[j];        }    }    return ans;}int main(){    int tcase;    scanf("%d",&tcase);    while(tcase--)    {        scanf("%s%s",S,T);        slen = strlen(S);        tlen = strlen(T);        printf("%d\n",KMP_Count());    }    return 0;}