Oulipo----poj3461（kmp模板）

题目链接：http://poj.org/problem?id=3461

和 减花布条 的题对比一下；

求s2中s1的个数kmp模板；

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N = 1e6+7;

char s1[N], s2[N];
int n, m, ans;
int Next[N];

void GetNext()
{
    int i = 0, j = -1;
    Next[i] = j;
    while(i<n)
    {
         if(j==-1 || s2[i] == s2[j])
            Next[++i] = ++j;
         else
            j = Next[j];
    }
}
void kmp()
{
    int i = 0, j = 0;
    while(i<m)
    {
        if(j==-1 || s1[i] == s2[j])
            i++,j++;
        else
            j = Next[j];
        if(j == n)
        {
            ans++;
            j=Next[j];
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s%s", s2, s1);
        m = strlen(s1);
        n = strlen(s2);
        GetNext();
        ans = 0;
        kmp();
        printf("%d
", ans);
    }
    return 0;
}