HDU 1686 Oulipo

http://acm.hdu.edu.cn/showproblem.php?pid=1686

求子串个数，可重复，直接上KMP模板

#include <iostream>
#include <queue>
using namespace std ; 
int n,m;
char a[1000002],b[10002];
int _next[1000002];
int ans;
void Init_()
{
    int i,k;  
    i = 0; k = -1; _next[0] = -1;  
    while(i < m){  
        if(k == -1 || b[i] == b[k]){  
            i++;k++;  
            if(b[i] != b[k])  
                _next[i] = k;  
            else  
                _next[i] = _next[k];  
        }  
        else  
            k = _next[k];  
    }  
}
void kmp()
{
    int i,j;  
    i = 0;j = 0;  
    while(i < n && j < m){  
        if(j == -1 || a[i] ==  b[j]){  
            i++;j++;  
        }  
        else  
            j = _next[j];
        if(j == m)
           {
               ans++;
            j=_next[j];
        }
    }    
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",b,a);
        n=strlen(a);
        m=strlen(b);
        Init_();
        ans=0;
        kmp();
        printf("%d\n",ans);
    }
    return 0;
}