【Gym103107E/黑龙江省赛16thE】Elastic Search（Trie树性质+ac自动机性质）

题目链接：https://codeforces.com/gym/103107/problem/E
题解连接：https://www.zhihu.com/question/459398759/answer/1887431805

补题过程

这里参考了题解的第二种解法，记录一下自己在补题过程中遇到的坑。

1. Trie树上子节点与其父节点的性质是父节点代表的串是子节点代表的串的前缀。
2. ac自动机上的fail树上子节点与其父节点的性质是父节点代表的串是子节点代表的串的后缀。

因为长度为 (|s|) 的串必然是由长度为 (|s-1|) 的串转移过来的，因此只需找长度为 (|s-1|) 作为前后缀的情况，记录最大值。

使用 (bfs) ，能够保证 (|s|) 小的串先被遍历到。

AC代码

#include <bits/stdc++.h>

#define ll long long
#define SZ(x) (int)x.size()
#define llinf 0x3f3f3f3f3f3f3f3f
#define pli pair<ll, int>
#define mp make_pair

using namespace std;
const int MAXN = 5e5 + 5;

class AC {
public:
    int T1[MAXN][26], top1;
    int T2[MAXN][26], top2;
    int fail[MAXN];
    int val[MAXN];
    queue<int> q;

    void init() {
        top1 = 1, top2 = 1;
        memset(T1[0], 0, sizeof(T1[0]));
        fail[0] = 0;
    }

    void insert1(char str[], int lenstr) {
        int u = 0;
        for (int i = 1; i <= lenstr; i++) {
            int ch = str[i] - 'a';
            if (!T1[u][ch]) {
                fail[top1] = 0;
                memset(T1[top1], 0, sizeof(T1[top1]));
                T1[u][ch] = top1++;
            }
            u = T1[u][ch];
        }
        val[u]++;
    }

    void insert2(char str[], int lenstr) {
        int u = 0;
        for (int i = 1; i <= lenstr; i++) {
            int ch = str[i] - 'a';
            if (!T2[u][ch]) {
                fail[top2] = 0;
                memset(T2[top2], 0, sizeof(T2[top2]));
                T2[u][ch] = top2++;
            }
            u = T2[u][ch];
        }
    }

    void build() {
        for (int i = 0; i < 26; i++) {
            if (T1[0][i]) {
                fail[T1[0][i]] = 0;
                q.push(T1[0][i]);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (T1[u][i]) {
                    fail[T1[u][i]] = T1[fail[u]][i];
                    q.push(T1[u][i]);
                } else T1[u][i] = T1[fail[u]][i];
            }
        }
    }

    int dp[MAXN];


    struct node {
        int id, fa;
    };

    int bfs() {
        int ans = 1;
        dp[0] = 0;
        queue<node> tq;
        for (int i = 0; i < 26; i++) {
            if (T2[0][i]) tq.push({T2[0][i], 0});
        }
        while (!tq.empty()) {
            node u = tq.front();
            tq.pop();
            dp[u.id] = max(dp[u.fa], dp[fail[u.id]]) + val[u.id];
            ans = max(ans, dp[u.id]);
            for (int i = 0; i < 26; i++) {
                if (T2[u.id][i]) tq.push({T2[u.id][i], u.id});
            }
        }
        return ans;
    }
    
} ac;

char str[MAXN];

int main() {
    ac.init();
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        ac.insert1(str, len);
        ac.insert2(str, len);
    }
    ac.build();
    printf("%d
", ac.bfs());
}