【SAM+线段树合并/SA+扫描线】CF1037H Security

Source
版权声明:这是蒟蒻的BLOG,神犇转载也要吱一声哦~ https://blog.csdn.net/Dream_Lolita/article/details/84716341

【题目】
原题地址
给定一个长度为 n n 的字符串 S S q q 个询问,每次询问形如 l   r   T l\ r\ T ,其中 T T 是一个字符串,表示询问 s l , , s r s_l,\dots,s_r 这个字符串中比 T T 字典序大的字典序最小的子串是什么,如没有则输出 1 -1
n 1 0 5 , q , S , T 2 × 1 0 5 n\leq 10^5,q,|S|,\sum |T|\leq 2\times 10^5

【解题思路1】
考虑每次询问如果没有询问区间的限制,我们在 SAM \text{SAM} 上进行匹配,那么我们每走一次只需要判断是否有一个比当前走的路大的后缀即可。显然最后一次可以比询问串大的分支是最后的答案。
现在有询问限制,我们可以用一个 26 26 的代价枚举接下来匹配的字符串是什么,然后看看再匹配后走到自动机上的点的 r i g h t right 集和代表的字符串是否在询问区间中即可。
我们可以用线段树合并来进行预处理出每个节点的right集。

T , S \sum |T|,|S| n n 同阶,复杂度是 O ( 26 n log n ) O(26n \log n) 的。

【解题思路2】
我们建出原串的 SA \text{SA}
如果我们知道询问串 T T 和答案串的 LCP \text{LCP} 的话,问题就转化为了 i i 下标在 [ a , b ] [a,b] r k rk 下标在 [ c , d ] [c,d] r k rk 最小的串。更具体的说,我们需要求出 i i 下标在 [ l , r l c p ( t , s a [ r k ( t ) + 1 ] ) ] , r k > r k t [l,r-lcp(t,sa[rk(t)+1])],rk>rk_t r k rk 最小的串,且 i > m a x ( l 1 , r l c p ( t , s a [ r k ( t ) + 1 ] ) ) i>max(l-1,r-lcp(t,sa[rk(t)+1]))

我们发现这就是一个二维数点问题,按 r k rk 排序后扫描线,用线段树维护询问即可。
这样做的复杂度是 O ( n log n ) O(n\log n) 的,比 SAM \text{SAM} 不知道高到哪里去了。

【参考代码】
SAM + \text{SAM}+ 线段树合并

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

const int N=1e6+10,M=N*26;
int n,Q,rt[N];
char s[N];

struct Segment
{
	int sz,ls[M],rs[M];bool w[M];
	void pushup(int x){w[x]=w[ls[x]]|w[rs[x]];}
	void update(int &x,int l,int r,int p)
	{
		if(!x) x=++sz;
		if(l==r){w[x]=1;return;}
		int mid=(l+r)>>1;
		if(p<=mid) update(ls[x],l,mid,p);
		else update(rs[x],mid+1,r,p);
		w[x]=w[ls[x]]|w[rs[x]];
	}
	int merge(int x,int y,int l,int r)
	{
		if(!x || !y) return x+y;
		int z=++sz,mid=(l+r)>>1;
		if(l==r) w[z]=w[x]|w[y];
		else
		{
			ls[z]=merge(ls[x],ls[y],l,mid);
			rs[z]=merge(rs[x],rs[y],mid+1,r);
			pushup(z);
		}
		return z;
	}
	bool query(int x,int l,int r,int L,int R)
	{
		if(!x || l>r) return 0;
		if(L<=l && r<=R) return w[x];
		int mid=(l+r)>>1;bool res=0;
		if(L<=mid) res|=query(ls[x],l,mid,L,R);
		if(R>mid) res|=query(rs[x],mid+1,r,L,R);
		return res;
	}
}T;

struct SAM
{
	int sz,las,fa[N],mx[N],ch[N][26];
	vector<int>g[N];
	void init(){sz=las=1;}
	void extend(int x)
	{
		int p,q,np,nq;
		p=las;las=np=++sz;mx[np]=mx[p]+1;
		for(;p && !ch[p][x];p=fa[p]) ch[p][x]=np;
		if(!p) fa[np]=1;
		else
		{
			q=ch[p][x];
			if(mx[q]==mx[p]+1) fa[np]=q;
			else
			{
				nq=++sz;mx[nq]=mx[p]+1;
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq;
			}
		}
	}
	void dfs(int x)
	{
		for(int i=0;i<(int)g[x].size();++i)
		{
			int v=g[x][i];
			dfs(v);rt[x]=T.merge(rt[x],rt[v],1,n);
		}
	}
	void merge(){for(int i=1;i<=sz;++i) g[fa[i]].pb(i);dfs(1);}
	void solve(char *s,int l,int r)
	{
		int len=strlen(s+1),p=1,pos=0,res=0;
		for(int i=1;i<=len+1;++i)
		{
			int c=i>len?0:(s[i]-'a'+1),flag=0;
			for(int j=c;j<26;++j) if(ch[p][j])
			{
				int x=ch[p][j];
				if(T.query(rt[x],1,n,l+i-1,r)){res=j+'a';pos=i-1;break;}
			}
			if(c && ch[p][c-1]) p=ch[p][c-1]; else break;
		}
		if(!res){puts("-1");return;}
		for(int i=1;i<=pos;++i) putchar(s[i]);
		putchar(res);puts("");
	}
}S;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("CF1037H.in","r",stdin);
	freopen("CF1037H.out","w",stdout);
#endif
	scanf("%s",s+1);n=strlen(s+1);S.init();
	for(int i=1;i<=n;++i) S.extend(s[i]-'a'),T.update(rt[S.las],1,n,i);
	S.merge();
	
	scanf("%d",&Q);
	while(Q--)
	{
		int l,r;scanf("%d%d%s",&l,&r,s+1);
		S.solve(s,l,r);
	}

	return 0;
}

SA + \text{SA}+ 扫描线

#include<bits/stdc++.h>
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
using namespace std;

const int N=5e5+10,INF=66666666;
int n,Q;
int beg[N],Log[N],len[N],le[N],ri[N],ord[N],a[N],ans[N][2];
char s[N],t[N];

namespace SA
{
	int rk[N],height[N],h[N][20];
	int wa[N],wb[N],wx[N],wy[N],sa[N];
	bool cmp(int *r,int a,int b,int l) {return r[a]==r[b] && r[a+l]==r[b+l];}
	void getsa(int *r,int n,int m)
	{
		int *x=wa,*y=wb,*t,i,j,p;
		for(i=0;i<m;++i) wx[i]=0;
		for(i=0;i<n;++i) wx[x[i]=r[i]]++;
		for(i=1;i<m;++i) wx[i]+=wx[i-1];
		for(i=n-1;~i;--i) sa[--wx[x[i]]]=i;
		for(j=1,p=0;p<n;j<<=1,m=p)
		{
			for(p=0,i=n-j;i<n;++i) y[p++]=i;
			for(i=0;i<n;++i) if(sa[i]>=j) y[p++]=sa[i]-j;
			for(i=0;i<n;++i) wy[i]=x[y[i]];
			for(i=0;i<m;++i) wx[i]=0;
			for(i=0;i<n;++i) wx[wy[i]]++;
			for(i=1;i<m;++i) wx[i]+=wx[i-1];
			for(i=n-1;~i;--i) sa[--wx[wy[i]]]=y[i];
			for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;++i) 
				x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
		}
	}
	void getheight(int *a)
	{
		int i,j,k=0;
		for(i=1;i<=n;++i) rk[sa[i]]=i;
		for(i=0;i<n;height[rk[i++]]=k)
			for(k?k--:0,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
		for(int i=0;i<=n;++i) h[i][0]=height[i];
		for(int j=1;j<20;++j) for(int i=1;i+(1<<j-1)<=n;++i) 
			h[i][j]=min(h[i][j-1],h[i+(1<<j-1)][j-1]);
	}
	int calc(int l,int r){if(l==r)return h[l][0];int t=Log[r-l+1];return min(h[l][t],h[r-(1<<t)+1][t]);}
	int lcp(int x,int y){x=rk[x];y=rk[y];if(x>y)swap(x,y);return calc(x+1,y);}
}
using SA::getsa;
using SA::getheight;
using SA::lcp;
using SA::sa;
using SA::rk;
using SA::h;

namespace Segment
{
	int w[N<<2];
	void build(int x,int l,int r)
	{
		w[x]=INF;
		if(l==r)return;
		int mid=(l+r>>1);
		build(ls,l,mid);build(rs,mid+1,r);
	}
	void update(int x,int l,int r,int p,int v)
	{
		if(l==r && l==p){w[x]=min(w[x],v);return;}
		int mid=(l+r)>>1;
		if(p<=mid) update(ls,l,mid,p,v);
		else update(rs,mid+1,r,p,v);
		w[x]=min(w[ls],w[rs]);
	}
	int query(int x,int l,int r,int L,int R)
	{
		if(L<=l && r<=R) return w[x];
		int mid=(l+r)>>1,ret=INF;
		if(L<=mid) ret=query(ls,l,mid,L,R);
		if(R>mid) ret=min(ret,query(rs,mid+1,r,L,R));
		return ret;
	}
};
using Segment::build;
using Segment::update;
using Segment::query;

bool cmpp(int x,int y){return rk[beg[x]]>rk[beg[y]];}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("CF1037H.in","r",stdin);
	freopen("CF1037H.out","w",stdout);
#endif
	Log[0]=-1;for(int i=1;i<N;++i) Log[i]=Log[i>>1]+1;
	scanf("%s%d",s,&Q);n=strlen(s);s[n++]='a'-1;
	for(int i=0;i<Q;++i)
	{
		scanf("%d%d%s",&le[i],&ri[i],t);
		beg[i]=n+1;ord[i]=i;
		// printf("%d\n",beg[i]);
		for(len[i]=0;t[len[i]];++len[i]) s[n++]=t[len[i]];
		s[n++]='a'-1;
	}
	for(int i=0;i<n;++i) a[i]=s[i]-'a'+2; a[n]=0;
	getsa(a,n+1,30);getheight(a);
	for(int i=n;i;--i) rk[i]=rk[i-1];rk[0]=0;
	for(int i=0;i<=n;++i) ++sa[i];
	// for(int i=0;i<n;++i) putchar(s[i]);puts("");
	// for(int i=0;i<=n;++i) printf("%d ",sa[i]);puts("");
	// for(int i=0;i<=n;++i) printf("%d ",rk[i]);puts("");
	// for(int i=0;i<=n;++i) printf("%d ",h[i][0]);puts("");
	sort(ord,ord+Q,cmpp);
	// for(int i=0;i<n;++i) printf("%d ",ord[i]);puts("");
	build(1,1,N-10);
	for(int i=0,las=n+1;i<Q;++i)
	{
		int j=ord[i],p=rk[beg[j]];
		if(p==n){ans[j][0]=-1;continue;}
		while(las>p)--las,update(1,1,N-10,sa[las],las);
		int L=min(h[p+1][0],len[j]),k;
		// printf("%d %d\n",i,L);
		if(ri[j]-L>=le[j])
		{
			k=query(1,1,N-10,le[j],ri[j]-L);
			// printf("query:%d %d\nfind:%d\n",le[j],ri[j]-L,k);
			if(k<=n)
			{
				ans[j][0]=sa[k];
				ans[j][1]=lcp(ans[j][0],beg[j])+1;
			}
		}
		for(int k=max(ri[j]-L+1,le[j]);k<=ri[j];++k)
		{
			if(rk[k]>p)
			{
				int t=lcp(k,beg[j]);
				// printf("lcp:%d %d %d\n",t,k,ri[j]);
				if(k+t<=ri[j]){if(!ans[j][0] || rk[ans[j][0]]>rk[k]) ans[j][0]=k,ans[j][1]=t+1;}
			} 
		}
		if(!ans[j][0]) ans[j][0]=-1;
		// puts("");
	}
	// for(int i=0;i<Q;++i) printf("%d %d\n",ans[i][0],ans[i][1]);
	for(int i=0;i<Q;++i)
	{
		if(!~ans[i][0]) puts("-1");
		else
		{
			for(int j=0;j<ans[i][1];++j) putchar(s[ans[i][0]+j-1]);
			puts("");
		}
	}

	return 0;
}

【总结】
码力巨菜,本来是抽时间写的代码占用了太多时间。
这周因为是考试周就不写代码了。