Keywords Search

模板题

点亮技能树！！AC自动机！！！！

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int max_n = 1e6 + 100;
struct AC_Automation {
    int teir[max_n][27];
    int fail[max_n];
    int is[max_n];
    int cnt = 1;
    void init() {
        for (int i = 0;i < max_n;++i)for (int j = 0;j <= 26;++j)teir[i][j] = 0;
        for (int i = 0;i < max_n;++i)fail[i] = is[i] = 0;cnt = 1;
    }void insert(char* p) {
        int cur = 0;
        int size = strlen(p);
        for (int i = 0;i < size;++i) {
            if (teir[cur][p[i] - 'a' + 1])
                cur = teir[cur][p[i] - 'a' + 1];
            else {
                teir[cur][p[i] - 'a' + 1] = cnt++;
                cur = teir[cur][p[i] - 'a' + 1];
            }
        }is[cur]++;
    }void build() {
        queue<int> que;
        for (int i = 1;i <= 26;++i) {
            if (teir[0][i]) {
                que.push(teir[0][i]);
                fail[teir[0][i]] = 0;
            }
        }while (!que.empty()) {
            int u = que.front();que.pop();
            for (int i = 1;i <= 26;++i)
                if (teir[u][i]) {
                    fail[teir[u][i]] = teir[fail[u]][i];
                    que.push(teir[u][i]);
                }
                else teir[u][i] = teir[fail[u]][i];
        }
    }int quiry(char* s) {
        int size = strlen(s);
        int cur = 0;int ans = 0;
        for (int i = 0;i < size;++i) {
            cur = teir[cur][s[i] - 'a' + 1];
            for (int j = cur; j && is[j]; j = fail[j]) {
                ans += is[j];
                is[j] = 0;
            }
        }return ans;
    }
}ac;
char p[max_n];
char s[max_n];
int main() {
    ios::sync_with_stdio(0);
    int T;cin >> T;
    while (T--) {
        int n;cin >> n;
        ac.init();
        while (n--) {
            cin >> p;
            ac.insert(p);
        }ac.build();
        cin >> s;
        cout << ac.quiry(s) << endl;
    }
}