#include<string>
#include<iostream>
using namespace std;
vector<int> getnext(string s) {
    vector<int> next(s.size(),0);
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < s.size();i++) {
        if (j > 0 && s[i] != s[j]) {
            j = next[j - 1]; //类似于动态规划,当前未知不相等，就回退到j-1 的位置，这个位置计算好了
        }
        if (s[i] == s[j]) {
            j++;
            next[i] = j;
        }

   }
    for (auto &k : next) {
        cout << k;
    }
    cout << endl;
    return next;
}
int kmp(string S, string T) {
    int res = 0;
    int i = 0;
    int j = 0;
    vector<int> next = getnext(S);
    for (int i = 0; i < T.size(); i++) {
        if (j > 0 && T[i] != S[j]) {
            j = next[j - 1];
        }
        if (T[i] == S[j]) {
            j++;
        }
        if (j == S.size()) {
            res++;
        }
    }
    cout << res << endl;
    return res;

}



int main() {
    string s = "aabaaab";
    string t = "abaaabaaabcd";
    kmp(s,t);
}