c/c++语言开发共享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; }