HOJ 1686 Oulipo（KMP, 裸题）

KMP, 裸题
题目意思：
给出a, b 两个字符串，长度分别是 n, m， 求字符串a 在b 中出现的次数。
本题要点：
1、先求出 a 字符串的 next 数组
2、然后在b 字符串 中匹配，指针i指向 b， 指针 j指向a， 当 j == n, j 回溯
j = Next[j];

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int MaxN = 10010, MaxM = 1000010;
char a[MaxN], b[MaxM];
int Next[MaxN];
int T, n, m;void getNext()
{
    n = strlen(a + 1);Next[1] = 0;for(int i = 2, j = 0; i <= n; ++i){
    while(j > 0 && a[i] != a[j + 1])j = Next[j];if(a[i] == a[j + 1])++j;Next[i] = j;}
}void solve()
{
    getNext();m = strlen(b + 1);int ans = 0;for(int i = 1, j = 0; i <= m; ++i){
    while(j > 0 && (j == n || b[i] != a[j + 1]))j = Next[j];if(b[i] == a[j + 1])++j;if(j == n){
    ++ans;}}printf("%d\n", ans);
}int main()
{
    scanf("%d", &T);while(T--){
    scanf("%s", a + 1);scanf("%s", b + 1);solve();}return 0;
}/* 3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN *//* 1 3 0 */