[POJ][3461][KMP] Oulipo

前言

---

题目大意

---

思路

---

代码

---

#include
#include
using namespace std;
#define T_SIZE 1000000
#define P_SIZE 10000
int next[P_SIZE+2];
char T[T_SIZE+2],P[P_SIZE+2];
//T是被匹配的串。
//P是模式串。
void COMPUTE_PREFIX_FUNCTION(char P[])
{
    int m=strlen(P+1);
    next[1]=0;
    for(int k=0,q=2;q<=m;q++)
    {
        while(k>0&&P[k+1]!=P[q])
            k=next[k];
        if(P[k+1]==P[q])
            k++;
        next[q]=k;
    }
}
int KMP_MATCHER(char T[],char P[])
{
    int n=strlen(T+1),m=strlen(P+1);
    COMPUTE_PREFIX_FUNCTION(P);
    int sum=0;
    for(int i=1,q=0;i<=n;i++)
    {
        while(q>0&&P[q+1]!=T[i])
            q=next[q];
        if(P[q+1]==T[i])
            q++;
        if(q==m)
        {
            sum++;
            q=next[q];
        }
    }
    return sum;
}
int main()
{
    int t;
    for(scanf("%d",&t);t>0;t--)
    {
        scanf("%s%s",P+1,T+1);
        //字符串都是从下标1开始的。 
        printf("%d\n",KMP_MATCHER(T,P));
    }
}