lessons/参考实现/04-KMP与Manacher/POJ-3461.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests; cin >> tests;
    while (tests--) {
        string pattern, text; cin >> pattern >> text;
        vector<int> pi(pattern.size());
        for (int i = 1; i < static_cast<int>(pattern.size()); ++i) {
            int j = pi[i - 1];
            while (j > 0 && pattern[i] != pattern[j]) j = pi[j - 1];
            if (pattern[i] == pattern[j]) ++j;
            pi[i] = j;
        }
        int matched = 0, answer = 0;
        for (char c : text) {
            while (matched > 0 && c != pattern[matched]) matched = pi[matched - 1];
            if (c == pattern[matched]) ++matched;
            if (matched == static_cast<int>(pattern.size())) {
                ++answer;
                matched = pi[matched - 1];
            }
        }
        cout << answer << '\n';
    }
}