考虑 AC 自动机,首先考虑答案构成。

对于一个单词,需要出现在字典中,则一定是单词成为了字典的某一部分。

为了思考方便,我们只考虑统计前缀,所以单词的出现就是单词为字典内某个单词后缀的前缀匹配。

而 AC 自动机的一个性质是:如果我们把 Fail 指针看成树边,根节点为 0 号节点,那么一个节点的子树内就是其所有的后缀。

这样我们就把问题转化为了求子树内标记和的问题。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
const int M = 200 + 5;

struct Node {
    int son[26], fail;
} tr[N];

int cnt;
int End[N];
int sz[N * 26];

void insert(string s, int id) {
    int n = s.length(), u = 0;
    for (int i = 0; i < n; i++) {
        int p = s[i] - 'a';
        if (!tr[u].son[p]) tr[u].son[p] = ++cnt;
        u = tr[u].son[p];
        sz[u]++;
    }
    End[id] = u;
}

int q[N];
int l = 0, r = -1;

void build() {
    for (int i = 0; i < 26; i++)
        if (tr[0].son[i]) q[++r] = tr[0].son[i];
    while (l <= r) {
        int u = q[l++];
        for (int i = 0; i < 26; i++) {
            if (tr[u].son[i]) {
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                q[++r] = tr[u].son[i];
            } else
                tr[u].son[i] = tr[tr[u].fail].son[i];
        }
    }
}

int n;
string s[M];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        insert(s[i], i);
    }
    build();
    for (int i = cnt; i >= 1; i--) sz[tr[q[i]].fail] += sz[q[i]];
    for (int i = 1; i <= n; i++) cout << sz[End[i]] << '\n';
    return 0;
}
最后修改:2020 年 08 月 30 日 12 : 27 AM
如果觉得我的文章对你有用,请随意赞赏