POJ 3461 Oulipo KMP练习

题目链接

题目很长，其实就是字符串匹配。

所以，权当练习 KMP

#include <cstdio>
#include <cstring>
#define MB 10101
#define MA 1000100
char a[MA],b[MB];
int next[MB];

void prekmp(char* b) {
    next[0]=-1;
    int j=-1;
    for ( int i(1); b[i]; i++) {
        while ( j!=-1 && b[i]!=b[j+1]) j=next[j];
        if ( b[i]==b[j+1] ) j++;
        next[i]=j;
    }
}

int kmp(char *a,char *b) {
    int j=-1,ans=0;
    for ( int i(0); a[i]; i++) {
        while ( j!=-1 && a[i]!=b[j+1] ) j=next[j];
        if (a[i]==b[j+1]) j++;
        if (!b[j+1]) {
            ans++;
            j=next[j];
        }
    }
    return ans;
}

int main() {
    int T;
    freopen("in.txt","r",stdin);
    for (scanf("%d\n",&T); T--;) {
        scanf("%s\n%s\n",b,a);
        memset(next,0,sizeof(0));
        prekmp(b);
        printf("%d\n",kmp(a,b));
    }
    return 0;
}