ZJM 与纸条

ZJM 的女朋友是一个书法家，喜欢写一些好看的英文书法。有一天 ZJM 拿到了她写的纸条，纸条上的字暗示了 ZJM 的女朋友 想给 ZJM 送生日礼物。ZJM 想知道自己收到的礼物是不是就是她送的，于是想看看自己收到的礼物在纸条中出现了多少次。

Input
第一行输入一个整数代表数据的组数

每组数据第一行一个字符串 P 代表 ZJM 想要的礼物, 包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 并且字符串长度满足 1 ≤ |P| ≤ 10,000 (|P| 代表字符串 P 的长度).
接下来一行一个字符串 S 代表 ZJM 女朋友的纸条, 也包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 满足 |P| ≤ |S| ≤ 1,000,000.
Output
输出一行一个整数代表 P 在 S中出现的次数.

Sample Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output

1
3
0

思路:

找符合条件的连续子串；
暴力匹配会超时；
选择KMP算法；

代码:

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e4 + 5;
const int maxm = 1e6 + 5;
int Next[maxn];
char str[maxm], ptr[maxn];

void get_next(const char str[])
{
    int len = strlen(str);
    Next[0] = 0;
    for (int i = 1, j = 0; i < len; i++)
    {
        while (j && str[i] != str[j])
            j = Next[j - 1];
        if (str[j] == str[i])
            j++;
        Next[i] = j;
    }
}
int KMP(const char str[], const char ptr[])
{
    int len1 = strlen(str);
    int len2 = strlen(ptr);
    int j = 0, ans = 0;//ans 记录成功匹配次数
    get_next(ptr);
    for (int i = 0; i < len1; i++)
    {
        while (j && ptr[j] != str[i])
            j = Next[j - 1];
        if (ptr[j] == str[i])
            j++;
        if (j == len2)
        {  //匹配到模式串末尾
            ans++;
            j = Next[j - 1];   //根据next数组转移
        }
    }
    return ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++)
    {
        memset(Next, 0, sizeof(Next));
        scanf("%s", &ptr);
        scanf("%s", &str);
        printf("%d\n", KMP(str, ptr));
    }
    return 0;
}