FG: First of Her Name 题解

· · 题解

题目大意

给定一棵 n 个节点的 Trie 树，进行 k 次询问，每次询问一个串 str 与 Trie 树上从任意一个节点开始走到根路径上形成的串中，有多少个串满足 str 是其前缀。

1 \leq n,k,\sum|str| \leq 10^6

题目解法

考虑 Trie 树上每一个串对所有询问串的贡献。不难发现，如果我们对询问串的反串建 AC 自动机（此时要求的条件是询问串是 Trie 树上的串的后缀），那么对于一个串 S，它在 AC 自动机中出现过的所有后缀，一定是 fail 树上的一条到根节点的链。我们只需要用 S 在 AC 自动机上暴力匹配，就能找到最长的那一个后缀。打一个前缀和标记最后进行一遍 DFS 即可。

现在我们需要对 Trie 树上所有点代表的字符串跑一遍匹配。由于 Trie 树上的子节点所代表的串在 AC 自动机上跑到的匹配是可以直接用其父节点匹配的位置跳一步转移就可以到达的。利用 Trie 图的小 trick 就能做到 O(n + k + |str|)。

Code：

const int MAXN = 1000010;

int tr[MAXN][26];
int res[MAXN];
int pos[MAXN];

char str[MAXN];
vector<int>to[MAXN];

struct ACAM {
    int tr[MAXN][26];
    int fail[MAXN];
    int cnt[MAXN];
    int ct;

    inline int Insert(int n) {
        int x = 0;
        for(int i = n; i >= 1; i--) {
            int c = str[i] - 'A';
            if(!tr[x][c])
                tr[x][c] = ++ct;
            x = tr[x][c];
        } return x;
    }

    inline void build() {
        queue<int>q;
        for(int i = 0; i < 26; i++)
            if(tr[0][i]) q.push(tr[0][i]);
        while(!q.empty()) {
            int x = q.front(); q.pop();
            for(int c = 0; c < 26; c++)
                if(tr[x][c]) fail[tr[x][c]] = tr[fail[x]][c], q.push(tr[x][c]);
                else tr[x][c] = tr[fail[x]][c];
        }
        for(int i = 1; i <= ct; i++)
            to[fail[i]].push_back(i);
    }

    inline void dfs(int x) {
        int sz = to[x].size();
        for(int i = 0; i < sz; i++)
            dfs(to[x][i]), cnt[x] += cnt[to[x][i]];
    }
}ac;

inline void dfs(int x, int y) {
    ac.cnt[y]++;
    for(int c = 0; c < 26; c++)
        if(tr[x][c]) dfs(tr[x][c], ac.tr[y][c]);
}

int main() {
    int n = ri, k = ri;
    for(int i = 1; i <= n; i++) {
        char ch = ge;
        while(!isalpha(ch)) ch = ge;
        tr[ri][ch - 'A'] = i;
    }
    for(int i = 1; i <= k; i++) {
        char ch = ge; int len = 0;
        while(!isalpha(ch)) ch = ge;
        while(isalpha(ch)) str[++len] = ch, ch = ge;
        pos[i] = ac.Insert(len);
    } ac.build(), dfs(0, 0), ac.dfs(0);
    for(int i = 1; i <= k; i++) printf("%d\n", ac.cnt[pos[i]]);
    return 0;
}