字符串

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

1<=n,m<=100,000,

分析

参照Dream_maker_yk和wzj的题解。

查前缀我们就把串反着插入，这时候状态该有一个left集合。

在这个反串的SAM上，两个点的最长公共前缀是两个点parent树上lca的len.

我们对于parent树中的每个节点，都维护他的子树中出现了字符串中的哪些节点，即left集合。这个可用线段树合并。

二分答案x，倍增找到c的祖先中len>=x的最浅的节点，判断该节点的left集合中是否出现了[a,b-x+1]。

时间复杂度\(O(n \log^2 n)\)

co int N=2e5;

namespace T{ // Interval Tree

	int tot,root[N],lc[N*20],rc[N*20];

	void insert(int&x,int l,int r,int p){

		x=++tot;

		if(l==r) return;

		int mid=l+r>>1;

		if(p<=mid) insert(lc[x],l,mid,p);

		else insert(rc[x],mid+1,r,p);

	}

	int merge(int x,int y){

		if(!x||!y) return x+y;

		int z=++tot;

		lc[z]=merge(lc[x],lc[y]),rc[z]=merge(rc[x],rc[y]);

		return z;

	}

	int query(int x,int l,int r,int ql,int qr){

		if(!x) return 0;

		if(ql<=l&&r<=qr) return 1;

		int mid=l+r>>1;

		if(qr<=mid) return query(lc[x],l,mid,ql,qr);

		if(ql>mid) return query(rc[x],mid+1,r,ql,qr);

		return query(lc[x],l,mid,ql,qr)||query(rc[x],mid+1,r,ql,qr);

	}

}

int n,m;

char s[N];

int last=1,tot=1; // Suffix Automaton

int ch[N][26],fa[N],len[N],pos[N]; // pos: out->in

void extend(int c,int po){

	int p=last,cur=last=++tot;

	len[cur]=len[p]+1,pos[po]=cur;

	T::insert(T::root[cur],1,n,po);

	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;

	if(!p) fa[cur]=1;

	else{

		int q=ch[p][c];

		if(len[q]==len[p]+1) fa[cur]=q;

		else{

			int clone=++tot;

			memcpy(ch[clone],ch[q],sizeof ch[q]);

			fa[clone]=fa[q],len[clone]=len[p]+1;

			fa[cur]=fa[q]=clone;

			for(;ch[p][c]==q;p=fa[p]) ch[p][c]=clone;

		}

	}

}

int cnt[N],ord[N],anc[N][19];

int check(int x,int a,int b,int p){

	for(int i=18;i>=0;--i)

		if(len[anc[p][i]]>=x) p=anc[p][i];

	return T::query(T::root[p],1,n,a,b-x+1);

}

int main(){

	read(n),read(m);

	scanf("%s",s+1);

	for(int i=n;i>=1;--i) extend(s[i]-'a',i);

	for(int i=1;i<=tot;++i) ++cnt[len[i]];

	for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1];

	for(int i=1;i<=tot;++i) ord[cnt[len[i]]--]=i;

	for(int i=tot;i;--i){

		int u=ord[i];

		T::root[fa[u]]=T::merge(T::root[fa[u]],T::root[u]);

	}

	for(int i=1;i<=tot;++i){ // edit 1: order isn't changeable

		int u=ord[i];

		anc[u][0]=fa[u];

		for(int j=1;j<=18;++j) anc[u][j]=anc[anc[u][j-1]][j-1];

	}

	for(int a,b,c,d;m--;){

		read(a),read(b),read(c),read(d);

		int l=0,r=std::min(b-a+1,d-c+1);

		while(l<r){

			int mid=l+r+1>>1;

			if(check(mid,a,b,pos[c])) l=mid;

			else r=mid-1;

		}

		printf("%d\n",l);

	}

	return 0;

}

巴特西

TJOI2016 字符串

字符串

分析

最新文章

热门文章