【題解】TIOJ 1306 字串中的字串

#include <bits/stdc++.h>
using namespace std;

int T, n;
vector <int> f;
string t, s;

void build(){
    f.clear();
    f.push_back(-1);
    int p1 = 0, p2 = -1;
    while (p1 < s.length()){
        if (p2 == -1 || s[p2] == s[p1]){
            p1++;
            p2++;
            f.push_back(p2);
        }
        else p2 = f[p2];
    }
}
int match(){
    int p1 = 0, p2 = 0, ans = 0;
    while (p1 < t.length()){
        if (p2 == -1 || t[p1] == s[p2]){
            p1++;
            p2++;
            if (p2 == s.length()){
                ans++;
                p2 = f[p2];
            }
        }
        else p2 = f[p2];
    }
    return ans;
}

int main(){
    cin >> T;
    while (T--){
        cin >> t;
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> s;
            build();
            cout << match() << "\n";
        }
    }
}