题目大意: 给两个串s1,s2。问s1在s2中成功匹配的次数。
解题思路: RT.

AC代码:

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

char Tmp[1000001],pattern[10001];
int prefix[10001];

void get_prefix_table (int n) {
    int i = 0, len = -1;
    prefix[0] = -1;
    while (i < n) {
        if(len == -1 || pattern[i] == pattern[len]) {
            i++;
            len++;
            prefix[i] = len;
        }else {
            len = prefix[len];
        }
    }
}

int kmp_search (int n, int m) {
    int ans = 0, i = 0, j = 0;
    get_prefix_table (m);
    while (i < n) {
        if(j == -1 || Tmp[i] == pattern[j]) {
            i++;
            j++;
        }else {
            j = prefix[j];
        }
        if(j == m) {
            ans++;
            j = prefix[j];
        }
    }
    return ans;
}

int main() {
    int T,n,m,i;
    scanf("%d",&T);
    while (T--) {
        scanf("%s%s", pattern, Tmp);
        printf("%d\n",kmp_search(strlen(Tmp),strlen(pattern)));
    }
    return 0;
}