题意
题目链接
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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605168.html