题解 CF666E 【Forensic Examination】
devout
2020-12-27 11:18:51
~~题号好评~~
**description**
给一个串 $s$ 和 $m$ 个串 $t_i$，每次询问 $l,r,pl,pr$ 求 $s[pl\cdots pr]$ 在 $t_l\sim t_r$ 中的哪个出现的最多，并求出现次数
$|s|\leq 5\times 10^5,m\leq 5\times 10^4,\sum|t_i|\leq 5\times 10^4,q\leq 5\times 10^5$
**solution**
SAM+线段树合并
首先对于所有的 $t_i$ 建出一棵广义SAM
我们知道，对于 SAM 上的每一个点，他的 parent tree 的子树里面的所有主串上的点的个数就是这个点对应的状态的出现次数，即所谓的 right 数组
同样的，对于广义 SAM 上的每一个点，我们用一棵线段树维护这个子树中每个不同的串的点数，利用线段树合并，我们就可以知道这个状态在任意的 $t_l\sim t_r$ 的出现次数。
但是 SAM 上每一个状态确定的是 $s$ 上的一个子串，如何确定 $s[pl\cdots pr]$ 对应的点呢？
我们首先可以对于 $s[1\cdots i]$ 确定每个点的匹配位置和匹配长度，也就是 [SP1811 LCS - Longest Common Substring](https://www.luogu.com.cn/problem/SP1811)
当询问 $s[pl\cdots pr]$ 时，先找到 $s[1\cdots pr]$ 的匹配位置，然后从这个点在 parent tree 上倍增，找到最靠上的 $maxlen\leq pr-pl+1$ 的点，这个点就包含了 $s[pl\cdots pr]$ 的全部出现情况，在这个点的线段树上进行区间查询就可以了
复杂度 $\mathcal O(|s|+\sum |t|\log \sum |t|)$
注意一些细节：
- 当 $t_l\sim t_r$ 中不存在 $s[pl\cdots pr]$ 时，应当输出 `l 0`
- 如果 $s[1\cdots pr]$ 的匹配长度小于 $pr-pl+1$ 时，也应该算作不存在
**code**
```cpp
#include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=5e5+5;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,m,q;
char s[N],t[N];
int link[N<<1],sam[N<<1][26],maxlen[N<<1];
int inde[N<<1],tpx[N<<1],topoxu;
int f[N<<1][21];
int p[N],l[N];
int samtot=1,lst;
vector<int> T[N<<1];
struct texas{
int lc,rc;
int max,pos;
}seg[N*2*20];
int root[N<<1],segtot;
void insert(int x,int id){
if(sam[lst][x]){
int p=lst,q=sam[lst][x];
if(maxlen[q]==maxlen[p]+1){
lst=q;
T[q].push_back(id);
}
else{
int clone=++samtot;
maxlen[clone]=maxlen[p]+1;
link[clone]=link[q];
T[clone].push_back(id);
memcpy(sam[clone],sam[q],sizeof(sam[q]));
for(;p&&sam[p][x]==q;p=link[p])sam[p][x]=clone;
link[q]=clone;
lst=clone;
}
return;
}
int now=++samtot,p;
maxlen[now]=maxlen[lst]+1;
T[now].push_back(id);
for(p=lst;p&&!sam[p][x];p=link[p])sam[p][x]=now;
if(!p)link[now]=1;
else{
int q=sam[p][x];
if(maxlen[q]==maxlen[p]+1)link[now]=q;
else{
int clone=++samtot;
maxlen[clone]=maxlen[p]+1;
link[clone]=link[q];
memcpy(sam[clone],sam[q],sizeof(sam[q]));
for(;p&&sam[p][x]==q;p=link[p])sam[p][x]=clone;
link[now]=link[q]=clone;
}
}
lst=now;
}
void pushup(int u){
if(seg[seg[u].lc].max>=seg[seg[u].rc].max)seg[u].max=seg[seg[u].lc].max,seg[u].pos=seg[seg[u].lc].pos;
else seg[u].max=seg[seg[u].rc].max,seg[u].pos=seg[seg[u].rc].pos;
}
void update(int &u,int l,int r,int x,int k){
if(!u)u=++segtot;
if(l==r){
seg[u].max+=k;
seg[u].pos=l;
return;
}
int mid=l+r>>1;
if(x<=mid)update(seg[u].lc,l,mid,x,k);
else update(seg[u].rc,mid+1,r,x,k);
pushup(u);
}
int merge(int u,int v,int l,int r){
if(!u||!v)return u|v;
int o=++segtot;
if(l==r){
seg[o].max=seg[u].max+seg[v].max;
seg[o].pos=l;
return o;
}
int mid=l+r>>1;
seg[o].lc=merge(seg[u].lc,seg[v].lc,l,mid);
seg[o].rc=merge(seg[u].rc,seg[v].rc,mid+1,r);
pushup(o);
return o;
}
texas query(int u,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr)return seg[u];
int mid=l+r>>1;
if(qr<=mid)return query(seg[u].lc,l,mid,ql,qr);
if(ql>mid)return query(seg[u].rc,mid+1,r,ql,qr);
texas L=query(seg[u].lc,l,mid,ql,qr);
texas R=query(seg[u].rc,mid+1,r,ql,qr);
if(L.max>=R.max)return L;
else return R;
}
void topo(){
queue<int> q;
Rep(i,2,samtot)inde[link[i]]++;
Rep(i,1,samtot)if(!inde[i])q.push(i);
Rep(i,1,samtot)
for(int j=0;j<T[i].size();j++)
update(root[i],1,m,T[i][j],1);
while(!q.empty()){
int u=q.front();q.pop();
tpx[++topoxu]=u;
if(u==1)continue;
int v=link[u];
root[v]=merge(root[v],root[u],1,m);
inde[v]--;
if(!inde[v])q.push(v);
}
_Rep(i,samtot,1){
int u=tpx[i];
f[u][0]=link[u];
Rep(j,1,20)f[u][j]=f[f[u][j-1]][j-1];
}
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
read(m);
Rep(i,1,m){
scanf("%s",t+1);
int len=strlen(t+1);
lst=1;
Rep(j,1,len)insert(t[j]-'a',i);
}
topo();
p[0]=1,l[0]=0;
Rep(i,1,n){
int x=s[i]-'a';
if(sam[p[i-1]][x])p[i]=sam[p[i-1]][x],l[i]=l[i-1]+1;
else{
for(p[i]=p[i-1];p[i]&&!sam[p[i]][x];p[i]=link[p[i]]);
if(!p[i]){
p[i]=1;
l[i]=0;
}
else{
l[i]=maxlen[p[i]]+1;
p[i]=sam[p[i]][x];
}
}
}
read(q);
while(q--){
int pl,pr,ql,qr;
read(ql),read(qr),read(pl),read(pr);
int x=p[pr];
if(l[pr]<pr-pl+1){
printf("%d 0\n",ql);
continue;
}
_Rep(i,20,0)
if(maxlen[f[x][i]]>=pr-pl+1)x=f[x][i];
texas u=query(root[x],1,m,ql,qr);
if(!u.max)printf("%d 0\n",ql);
else printf("%d %d\n",u.pos,u.max);
}
return 0;
}
```