POJ3461 Oulipo（KMP）

题目链接

KMP 模版题，求子串出现次数。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int next[10005];
char a[10005], b[1000005];
void kmp_pre(char x[],int m,int next[]){
    int i, j;
    j = next[0] = -1;
    i = 0;
    while(i < m){
        while(-1!=j && x[i]!=x[j])
            j = next[j];
        next[++i] = ++j;
    }
}

int KMP_Count(char x[], int m, char y[], int n){//x是模式串， y是主串
    int i, j;
    int ans = 0;
    //preKMP(x,m,next);
    kmp_pre(x, m, next);
    i = j = 0;
    while(i<n){
        while(-1!=j && y[i]!=x[j])
            j = next[j];
        i++;
        j++;
        if(j>=m){
            ans++;
            j = next[j];
        }
    }
    return ans;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    while(t--){
        scanf("%s %s", a, b);
        cout << KMP_Count(a, strlen(a), b, strlen(b)) << endl;
    }
    return 0;
}