AC自动机

向右看齐 2021-12-16 12:37 297阅读 0赞

存个板子

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e6 + 10;
    int trie[maxn][26]; 
    int flag[maxn];
    int fail[maxn];  
    int tol;
    
    void Insert(char *s) {
        int root = 0;
        int len = strlen(s);
        for (int i = 0; i < len; i++) {
            int id = s[i] - 'a';
            if (!trie[root][id]) trie[root][id] = ++tol;
            root = trie[root][id];
        }
        flag[root]++;
    }
    
    void getfail() {
        queue<int> que;
        for (int i = 0; i < 26; i++) {
            if (trie[0][i]) {
                que.push(trie[0][i]);
                fail[trie[0][i]] = 0;
            }
        }
        while (!que.empty()) {
            int now = que.front(); que.pop();
            for (int i = 0; i < 26; i++) {
                if (trie[now][i]) {
                    fail[trie[now][i]] = trie[fail[now]][i];
                    que.push(trie[now][i]);
                } else {
                    trie[now][i] = trie[fail[now]][i];
                }
            }
        }
    }
    
    int query(char *s) {
        int now = 0, ans = 0;
        int len = strlen(s);
        for (int i = 0; i < len; i++) {
            int id = s[i] - 'a';
            now = trie[now][id];
            int temp = now;
            while (temp) {
                ans += flag[temp];
                flag[temp] = 0;
                temp = fail[temp];
            }
        }
        return ans;
    }
    char s[1000000+10];
    int main() {
        int T;
        scanf("%d", &T);
        while (T--) {
            memset(trie, 0, sizeof trie);
            memset(fail, 0, sizeof fail);
            memset(flag, 0, sizeof flag);
            tol = 0;
            int n;
            scanf("%d", &n);
            for (int i = 0; i < n; i++) {
                scanf("%s", s);
                Insert(s);
            }
            getfail();
            scanf("%s", s);
            printf("%d\n", query(s));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Mrzdtz220/p/10680187.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/09a0a4506b9a4901a2a37da3f20fd71c.png