单词「TJOI 2013」(AC自动机)

传送门

我们正常的建好Trie后求一遍fail。之后对于每一个节点，从它的fail连向它一条单项边。然后从根节点开始dfs。

记sum[i]代表从根到i号节点所代表的的字符串出现的次数，即该点的权值。

设当前的节点为x，他有一个孩子y，则使sum[x] = sum[y]。

记得记录一下每个字符串结尾的节点编号，设第i个字符串结尾的编号为id[i]，对于每个字符串i最后输出sum[id[i]]即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector> 
using namespace std;
int trie[5000010][26], fail[5000010], sum[5000010], tot = 1;
int n;
int end_id[210];
char s[5000010];
queue<int> q;
vector<int> vec[5000010];
void solve(int x) {
    for (int i = 0; i < (int)vec[x].size(); i  ) {
        solve(vec[x][i]);
        sum[x]  = sum[vec[x][i]];
    }
}
int main() {
    cin >> n;
    for (int i = 1, p, len; i <= n; i  ) {
        scanf("%s", s   1);
        p = 1;
        len = strlen(s   1);
        for (int j = 1; j <= len; j  ) {
            int k = s[j] - ‘a‘;
            sum[p]  ;
            if (!trie[p][k]) trie[p][k] =   tot;
            p = trie[p][k];
        }
        sum[p]  ;
        end_id[i] = p;
    }
    for (int i = 0; i < 26; i  ) trie[0][i] = 1;
    fail[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 26; i  ) {
            if (!trie[x][i]) {
                trie[x][i] = trie[fail[x]][i];
            } else {
                vec[trie[fail[x]][i]].push_back(trie[x][i]);
                fail[trie[x][i]] = trie[fail[x]][i];
                q.push(trie[x][i]);
            }
        }
    }
    solve(1);
    for (int i = 1; i <= n; i  ) {
        cout << sum[end_id[i]] << "n";
    }
    return 0;
}