HDU 6138 Fleet of the Eternal Throne(后缀自动机)

题意

题目链接

sol

真是狗血，被疯狂卡常的原因竟是

我们考虑暴力枚举每个串的前缀，看他能在\(x, y\)的后缀自动机中走多少步，对两者取个min即可

复杂度\(o(t 10^5 m)\)(好假啊)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, m;
string s[maxn];
struct sam {
    int ch[maxn][26], fa[maxn], len[maxn], tot, las, root;
    void init() {
        for(int i = 0; i <= tot; i++) 
            fa[i] = 0, len[i] = 0, memset(ch[i], 0, sizeof(ch[i]));
        tot = root = 1; las = 1;
    }
    void insert(int x) {
        int now = ++tot, pre = las; las = now; len[now] = len[pre] + 1;
        for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;
        if(!pre) {fa[now] = root; return ;}
        int q = ch[pre][x];
        if(len[q] == len[pre] + 1) fa[now] = q;
        else {
            int nq = ++tot; fa[nq] = fa[q]; len[nq] = len[pre] + 1; fa[q] = fa[now] = nq;
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq;
        }
    }
    void build(string str) {
        init(); 
        for(auto &x: str) 
            insert(x - 'a');
    }
    int find(string str) {
        int cur = 0, now = root;
        for(auto &x : str) {
            int v = x - 'a';
            if(ch[now][v]) cur++, now = ch[now][v];
            else return cur;
        }
        return cur;
    }
}s[2];


void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    cin >> m;
    while(m--) {
        int x, y;
        cin >> x >> y;
        s[0].build(s[x]);
        s[1].build(s[y]);
        int ans = 0;
        for(int i = 1; i <= n; i++) 
            ans = max(ans, min(s[0].find(s[i]), s[1].find(s[i])));
        cout << ans << '\n';
    }   
}
int main() {
//  freopen("a.in", "r", stdin);
    ios::sync_with_stdio(0);
    int t; cin >> t;
    for(; t--; solve());
    return 0;
}