暴力水过去了……
有一个AC自动机上的解法
考场上想的是将 \(s\) 都扔到AC自动机上，设法用 \(t\) 去匹配但不太可做
发现 \(s\) 的后缀若是 \(t\) 的前缀，那从 \(s\) 不断跳fail指针能跳到 \(t\) 中的节点上
于是有想法是将询问离线，对每个 \(s\) 都跳一遍fail，但是会T
所以可以转化，枚举每个T，再枚举T上的每个节点，对其子树区间取max以更新答案
枚举过一个 \(T\) 后其再在线段树上的贡献要设法撤销一下
但还有另一个做法
发现 \(L = \sum |s_i| \leqslant 1e6\)
- 根号分治的又一种应用：当输入的一些字符串序列总长度为 \(L\)，题目要求对指定的一些序列对进行操作，且对一对序列操作的复杂度为 \(min(len_i, len_j)\) 时，可以考虑以 \(\sqrt L\) 为界分治
具体地，预处理所有 \(\geqslant \sqrt L\) 的序列对之间的贡献，而当询问中包含长度 \(< \sqrt L\) 的序列时爆算
复杂度 \((L+q)\sqrt L\)，调一下块的大小可以做到 \(l\sqrt q\)
其实是裸暴力的 Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 600010
#define ll long long
#define ull unsigned long long
//#define int long long
int n, q;
int len[N], mlen;
char s[N], *a[N];
ull *h[N], p[N];
const ull base=13131;
inline ull hashing(ull *h, int l, int r) {return h[r]-h[l-1]*p[r-l+1];}
namespace force{
void solve() {
for (int i=1,x,y; i<=q; ++i) {
scanf("%d%d", &x, &y);
int ans=0, lim=min(len[x], len[y]);
// cout<<"lim: "<<lim<<endl;
// cout<<a[y][1]<<' '<<a[x][len[x]]<<endl;
for (int j=1; j<=lim; ++j) if (hashing(h[x], len[x]-j+1, len[x])==hashing(h[y], 1, j)) ans=j;
printf("%d\n", ans);
}
exit(0);
}
}
namespace task1{
int rem[15][15];
void solve() {
for (int i=1; i<=n; ++i) {
for (int j=1; j<=n; ++j) {
int ans=0, lim=min(len[i], len[j]);
for (int k=1; k<=lim; ++k) if (hashing(h[i], len[i]-k+1, len[i])==hashing(h[j], 1, k)) ans=k;
rem[i][j]=ans;
}
}
for (int i=1,x,y; i<=q; ++i) {
scanf("%d%d", &x, &y);
printf("%d\n", rem[x][y]);
}
exit(0);
}
}
signed main()
{
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
scanf("%d%d", &n, &q);
p[0]=1;
for (int i=1; i<=n; ++i) {
scanf("%s", s+1);
len[i]=strlen(s+1); mlen=max(mlen, len[i]);
a[i]=new char[len[i]+5];
h[i]=new ull[len[i]+5];
for (int j=1; j<=len[i]+1; ++j) a[i][j]=s[j];
h[i][0]=0;
for (int j=1; j<=len[i]; ++j) h[i][j]=h[i][j-1]*base+a[i][j];
}
// cout<<"mlen: "<<mlen<<endl;
for (int i=1; i<=mlen; ++i) p[i]=p[i-1]*base;
if (n<=10) task1::solve();
else force::solve();
return 0;
}