题目

题目链接：https://codeforces.com/problemset/problem/666/E
给你一个串 \(S\) 以及一个字符串数组 \(T_{1\ldots m}\)，\(q\) 次询问，每次问 \(S\) 的子串 \(S[p_l\ldots p_r]\) 在 \(T_{l\ldots r}\) 中的哪个串里的出现次数最多，并输出出现次数。
如有多解输出最靠前的那一个。
\(|s|,\sum|t|,q\leq 5\times 10^5\)，\(m\leq 5\times 10^4\)。

思路

把所有 \(t\) 串的广义 SAM 建出来，对于 \(s\) 的每一个前缀 \(s[1\sim i]\)，在 SAM 上跑匹配找到它最长的能匹配的后缀所在的等价类的编号，以及这个后缀的长度。
对于一次询问，可以通过在 parent 树上倍增找到 \(s[pl,pr]\) 所在的等价类。注意如果 \(s[1\sim pr]\) 的最长后缀长度都没有 \(pr-pl+1\)，那么需要判无解。
那么问题转化为询问 parent 树上一个点的子树内 \(t_l\sim t_r\) 出现次数最多的是哪个串。这个问题就很经典了，对于 parent 树上每一个节点搞一棵动态开点线段树，区间 \([l,r]\) 维护 \(t_l\sim t_r\) 的串中出现次数最多的串的出现次数以及编号。从下往上线段树合并即可。
还需要注意如果没有一个串包含 \(s[pl\sim pr]\)，那么需要输出 L 0。
时间复杂度 \(O((q+\sum|t|)\log (\sum |t|))\)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=500010,LG=20;
int n,m,Q,rt[N],id[N],le[N];
char s[N],t[N];

struct SegTree
{
	int tot,lc[N*LG*4],rc[N*LG*4],maxn[N*LG*4],pos[N*LG*4];
	
	void pushup(int x)
	{
		if (maxn[lc[x]]>=maxn[rc[x]])
			maxn[x]=maxn[lc[x]],pos[x]=pos[lc[x]];
		else
			maxn[x]=maxn[rc[x]],pos[x]=pos[rc[x]];
	}
	
	int update(int x,int l,int r,int k,int v)
	{
		if (!x) x=++tot;
		if (l==r) { maxn[x]+=v; pos[x]=l; return x; }
		int mid=(l+r)>>1;
		if (k<=mid) lc[x]=update(lc[x],l,mid,k,v);
			else rc[x]=update(rc[x],mid+1,r,k,v);
		pushup(x);
		return x;
	}
	
	int merge(int x,int y,int l,int r)
	{
		if (!x || !y) return x|y;
		int p=++tot;
		if (l==r)
		{
			maxn[p]=maxn[x]+maxn[y]; pos[p]=l;
			return p;
		}
		int mid=(l+r)>>1;
		lc[p]=merge(lc[x],lc[y],l,mid);
		rc[p]=merge(rc[x],rc[y],mid+1,r);
		pushup(p);
		return p;
	}
	
	void query(int x,int l,int r,int ql,int qr,int &c,int &p)
	{
		if (ql<=l && qr>=r)
			return (void)(c=maxn[x],p=pos[x]);
		int mid=(l+r)>>1,c1=0,c2=0,p1=0,p2=0;
		if (ql<=mid) query(lc[x],l,mid,ql,qr,c1,p1);
		if (qr>mid) query(rc[x],mid+1,r,ql,qr,c2,p2);
		if (c1>=c2) c=c1,p=p1;
			else c=c2,p=p2;
	}
}seg;

struct SAM
{
	int last,tot,ch[N][26],fa[N],len[N],X[N],Y[N],f[N][LG+1];
	SAM() { tot=1; }
	
	void insert(int c,int i)
	{
		int p=last;
		if (ch[p][c])
		{
			int q=ch[p][c];
			if (len[q]==len[p]+1) last=q;
			else
			{
				int nq=++tot; last=nq;
				fa[nq]=fa[q]; len[nq]=len[p]+1;
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				fa[q]=nq;
				for (;p && ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
			}
		}
		else
		{
			int np=++tot; last=np;
			len[np]=len[p]+1;
			for (;p && !ch[p][c];p=fa[p]) ch[p][c]=np;
			if (!p) fa[np]=1;
			else
			{
				int q=ch[p][c];
				if (len[q]==len[p]+1) fa[np]=q;
				else
				{
					int nq=++tot;
					fa[nq]=fa[q]; len[nq]=len[p]+1;
					memcpy(ch[nq],ch[q],sizeof(ch[q]));
					fa[q]=fa[np]=nq;
					for (;p && ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
				}
			}
		}
		rt[last]=seg.update(rt[last],1,m,i,1);
	}
	
	void topsort()
	{
		for (int i=1;i<=tot;i++) X[len[i]]++;
		for (int i=1;i<=tot;i++) X[i]+=X[i-1];
		for (int i=1;i<=tot;i++) Y[X[len[i]]--]=i;
		for (int i=tot;i>=1;i--)
			if (fa[Y[i]]) rt[fa[Y[i]]]=seg.merge(rt[fa[Y[i]]],rt[Y[i]],1,m);
		for (int i=1,x;i<=tot;i++)
		{
			x=Y[i]; f[x][0]=fa[x];
			for (int j=1;j<=LG;j++)
				f[x][j]=f[f[x][j-1]][j-1];
		}
	}
	
	void match()
	{
		for (int i=1,p=1;i<=n;i++)
		{
			int c=s[i]-‘a‘;
			if (ch[p][c])
			{
				id[i]=p=ch[p][c]; le[i]=le[i-1]+1;
				continue;
			}
			while (p && !ch[p][c]) p=fa[p];
			le[i]=len[p]+1; id[i]=p=(p ? ch[p][c] : 1);
		}
	}
}sam;

int main()
{
	scanf("%s%d",s+1,&m);
	n=strlen(s+1);
	for (int i=1;i<=m;i++)
	{
		scanf("%s",t+1);
		sam.last=1;
		int len=strlen(t+1);
		for (int j=1;j<=len;j++)
			sam.insert(t[j]-‘a‘,i);
	}
	sam.topsort(); sam.match();
	scanf("%d",&Q);
	while (Q--)
	{
		int l,r,ql,qr;
		scanf("%d%d%d%d",&ql,&qr,&l,&r);
		int p=id[r],cnt=0,pos=0;
		if (le[r]<r-l+1) { cout<<ql<<" 0\n"; continue; }
		for (int i=LG;i>=0;i--)
			if (sam.len[sam.f[p][i]]>=r-l+1) p=sam.f[p][i];
		seg.query(rt[p],1,m,ql,qr,cnt,pos);
		if (!cnt) pos=ql;
		cout<<pos<<" "<<cnt<<"\n";
	}
	return 0;
}

【CF666E】Forensic Examination