题意

题目链接

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;
}