题解 | String Matching

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string t, s;
    cin >> t >> s;

    int s_size = s.size();
    vector<int> next(s_size);
    int p = 0, i = 1;

    while (i < s_size) {
        if (s[i] == s[p]) {
            next[i++] = ++p;
        }
        else {
            if (p == 0) {
                i++;
            }
            else {
                p = next[p - 1];
            }
        }
    }

    int cnt = 0;
    int j = 0, k = 0;

    while (j < t.size()) {
        if (s[k] == t[j] && k == s_size - 1) {
            cnt++;
            k = next[k];
            j++;
            continue;
        }
        if (s[k] == t[j]) {
            k++;
            j++;
        }
        else {
            if (k == 0) {
                j++;
            }
            else {
                k = next[k - 1];
            }
        }
    }

    cout << cnt << endl;
}