题目来源1
题目来源2:

当原串S为 aaaa ,模式串为 aa 时算作出现了 3 次.
终点是: 当j==plen 时, j=nxt[j]

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define end '\n'
#define IOS ios::sync_with_stdio(0)
int nxt[N];
void get_next(string p) {
    int len = p.size();
    int j = 0, k = -1;
    nxt[0] = -1;
    while (j < len) {
        if (k == -1 || p[j] == p[k]) {
            nxt[++j] = ++k;
        } else {
            k = nxt[k];
        }
    }
}
int get_num(string s,string p) {
    int ans = 0;
    int slen = s.size();
    int plen = p.size();
    get_next(p);
    int i = 0, j = 0;
    while (i < slen) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            j = nxt[j];
        }
        if (j == plen) {
            ans++;
            j = nxt[j];
        }
    }
    return ans;
}
int main() {
    IOS;
    int t;
    string s, p;
    cin >> t;
    while (t--) {
        cin >> p >> s;
        cout << get_num(s, p) << end;
    }
    return 0;
}
/*3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN 1 3 0*/