HDU1686 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 nextt[10010];

void preKMP(char x[], int m, int kmpNext[]){
    int i, j;
    j = kmpNext[0] = -1;
    i = 0;
    while(i<m){
        while(-1!=j && x[i]!=x[j])
            j = kmpNext[j];
        if(x[++i] == x[++j])
            kmpNext[i] = kmpNext[j];
        else kmpNext[i] = j;
    }
}

int KMP_Count(char x[], int m, char y[], int n){
    int i, j;
    int ans = 0;
    preKMP(x,m,nextt);
    i = j = 0;
    while(i<n){
        while(-1!=j && y[i]!=x[j])
            j = nextt[j];
        i++;
        j++;
        if(j>=m){
            ans++;
            j = nextt[j];
        }
    }
    return ans;
}


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