GYM103145L. k-th Smallest Common Substring
给出\(n\)个字符串。
询问第\(k\)小的公共子串。
做法：
将每个字符串逆序插入SAM，建出后缀树。
第一个需求，公共子串：
这里可以把每个字符串视为一种颜色，它在SAM上对应的每个终止节点染上这个颜色。
然后问题转化为询问一个节点的link树子树内是否有n种颜色。如果有，那么这个节点表示的子串就是公共子串。
这一步可以用树上差分做掉。
第二个需求，第k大。
可以通过代码里给出的排序方法，对后缀树做一个字典序排序。
这样dfs序就是字典序了。顺便完成了每个节点的endpos位置的存储。
然后将所有公共子串节点按照dfs序排序。
求一个前缀和数组，对每个询问k，在前缀和数组上二分，二分找到对应的节点，输出endpos位置，根据长度
这题就做完了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int nxt[maxn][26],link[maxn],len[maxn],lst=1,tot=1;
int c[maxn];
pair<int,int> edp[maxn];
int n,q;
vector<int> e[maxn];
void sam_extend (char c) {
int cur=++tot;
len[cur]=len[lst]+1;
int p=lst;
while (p&&!nxt[p][c-'a']) {
nxt[p][c-'a']=cur;
p=link[p];
}
if (!p) link[cur]=1;
else {
int q=nxt[p][c-'a'];
if (len[p]+1==len[q]) {
link[cur]=q;
}
else {
int clone=++tot;
len[clone]=len[p]+1;
for (int i=0;i<26;i++) nxt[clone][i]=nxt[q][i];
link[clone]=link[q];
while (p&&nxt[p][c-'a']==q) {
nxt[p][c-'a']=clone;
p=link[p];
}
link[q]=link[cur]=clone;
}
}
lst=cur;
}
vector<int> g[maxn];
int h[maxn],father[25][maxn],dfn[maxn],tol;
void init () {
for (int i=0;i<=tot;i++) {
g[i].clear();
e[i].clear();
h[i]=dfn[i]=link[i]=len[i]=c[i]=0;
edp[i]=make_pair(0,0);
for (int j=0;j<26;j++) {
nxt[i][j]=0;
}
}
lst=tot=1;
tol=0;
}
void dfs (int u) {
dfn[u]=++tol;
for (int v:g[u]) {
father[0][v]=u;
h[v]=h[u]+1;
dfs(v);
edp[u]=max(edp[u],edp[v]);
}
}
int lca (int x,int y) {
if (h[x]<h[y]) swap(x,y);
for (int i=20;i>=0;i--) if (h[x]-h[y]>>i) x=father[i][x];
if (x==y) return x;
for (int i=20;i>=0;i--) {
if (father[i][x]!=father[i][y]) {
x=father[i][x];
y=father[i][y];
}
}
return father[0][x];
}
vector<int> vv;
void cal (int u) {
dfn[u]=++tol;
for (int v:g[u]) {
cal(v);
c[u]+=c[v];
}
}
int _;
long long sum[maxn];
string s[maxn];
int main () {
ios::sync_with_stdio(false);
cin>>_;
int ff=0;
if (_>1) ff=1;
while (_--) {
cin>>n;
for (int i=n;i>=1;i--) {
lst=1;
cin>>s[i];
int mm=s[i].size();
for (int j=s[i].size()-1;j>=0;j--) {
sam_extend(s[i][j]);
e[i].push_back(lst);
edp[lst]=max(edp[lst],{i,mm-j});
}
}
for (int i=2;i<=tot;i++) g[link[i]].push_back(i);
dfs(1);
for (int i=1;i<=20;i++) for (int j=1;j<=tot;j++) father[i][j]=father[i-1][father[i-1][j]];
for (int i=1;i<=n;i++) {
sort(e[i].begin(),e[i].end(),[&](int x,int y) {
return dfn[x]<dfn[y];
});
for (int j=0;j<e[i].size();j++) c[e[i][j]]++;
for (int j=0;j<e[i].size()-1;j++) {
c[lca(e[i][j],e[i][j+1])]--;
}
}
for (int i=1;i<=tot;i++) sort(g[i].begin(),g[i].end(),[&](int x,int y) {
return s[edp[x].first][s[edp[x].first].size()-edp[x].second+len[i]]<s[edp[y].first][s[edp[y].first].size()-edp[y].second+len[i]];
});
vv.clear();
tol=0;
cal(1);
for (int i=2;i<=tot;i++) if (c[i]==n) vv.push_back(i);
sort(vv.begin(),vv.end(),[&](int x,int y) {
return dfn[x]<dfn[y];
});
int m=vv.size();
for (int i=1;i<=m;i++) sum[i]=sum[i-1]+len[vv[i-1]]-len[link[vv[i-1]]];
cin>>q;
while (q--) {
int k;
cin>>k;
int L=1,R=m,pp=-1;
while (L<=R) {
int mid=(L+R)>>1;
if (sum[mid]>=k) {
pp=mid;
R=mid-1;
}
else {
L=mid+1;
}
}
if (pp==-1) {
cout<<"-1\n";
continue;
}
k-=sum[pp-1];
int x=vv[pp-1];
//cout<<x<<'\n';
cout<<s[edp[vv[pp-1]].first].size()-edp[vv[pp-1]].second<<" "<<s[edp[vv[pp-1]].first].size()-edp[vv[pp-1]].second+len[link[vv[pp-1]]]+k<<'\n';
}
init();
}
}