UOJ #395 BZOJ 5417 Luogu P4770 [NOI2018]你的名字 (后缀自动机、线段树合并)

NOI2019考前做NOI2018题。。

题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=5417

(luogu) https://www.luogu.org/problemnew/show/P4770

(uoj) http://uoj.ac/problem/395

题解: 其实非常水，转化成\(S[l,r]\)和\(T\)有多少本质不同的公共子串，我们就是要求出串\(T\)每个位置与\(S[l,r]\)最长匹配的长度。那么就对\(S\)建SAM，把\(T\)在\(S\)上跑，每次到达一个点之后如果它的子树内没有\([l,r]\)之间的点就跳fa. 求子树内的点(即Right集合)可以自上而下线段树合并。因为要求本质不同的公共子串个数，那么对\(T\)也建立后缀自动机，统计T的后缀自动机上每个点与S的公共子串个数。细节挺多，挂了好几次，详见代码。

时间复杂度\(O(n\log n)\), \(n\)为输入字符串总长

字符串细节真的好多啊，提醒自己明天如果写字符串题一定要对拍！(快算了吧，我必不可能会做字符串)

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<iostream>

#include<algorithm>

#define llong long long

using namespace std;

inline int read()

{

	int x=0; bool f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	if(f) return x;

	return -x;

}

const int N = 5e5;

const int S = 26;

const int LGN = 21;

struct SuffixAutomaton

{

	int fa[(N<<1)+3];

	int len[(N<<1)+3];

	int son[(N<<1)+3][S+1];

	int ord[(N<<1)+3];

	int buc[(N<<1)+3];

	int rtn,siz,lstpos;

	void init()

	{

		for(int i=1; i<=siz; i++)

		{

			len[i] = fa[i] = 0;

			for(int j=1; j<=S; j++) son[i][j] = 0;

		}

		rtn = siz = lstpos = 1;

	}

	int insertchar(int ch)

	{

		int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1;

		for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}

		if(p==0) {fa[np] = 1;}

		else

		{

			int q = son[p][ch];

			if(len[q]==len[p]+1) {fa[np] = q;}

			else

			{

				siz++; int nq = siz; len[nq] = len[p]+1;

				memcpy(son[nq],son[q],sizeof(son[q]));

				fa[nq] = fa[q]; fa[np] = fa[q] = nq;

				for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}

			}

		}

		return np;

	}

	void getord()

	{

		for(int i=1; i<=siz; i++) buc[i] = 0;

		for(int i=1; i<=siz; i++) buc[len[i]]++;

		for(int i=1; i<=siz; i++) buc[i] += buc[i-1];

		for(int i=siz; i>=1; i--) ord[buc[len[i]]--] = i;

	}

} sam,samt;

struct SegmentTree

{

	int ls,rs;

} sgt[(N<<1)*LGN+3];

char a[N+3],b[N+3];

int mxl[(N<<1)+3];

int rt[(N<<1)+3];

int n,m,q,rtn,siz;

void addval(int &pos,int le,int ri,int lrb)

{

	siz++; sgt[siz] = sgt[pos]; pos = siz;

	if(le==lrb && ri==lrb) {return;}

	int mid = (le+ri)>>1;

	if(lrb<=mid) {addval(sgt[pos].ls,le,mid,lrb);}

	else {addval(sgt[pos].rs,mid+1,ri,lrb);}

}

int merge(int pos1,int pos2)

{

	if(pos1==0) return pos2; if(pos2==0) return pos1;

	siz++; int pos = siz;

	sgt[pos].ls = merge(sgt[pos1].ls,sgt[pos2].ls);

	sgt[pos].rs = merge(sgt[pos1].rs,sgt[pos2].rs);

	return pos;

}

int query(int pos,int le,int ri,int rb) //largest <=rb

{

	if(pos==0) return 0;

	if(le==ri) return le;

	int mid = (le+ri)>>1;

	if(rb<=mid) return query(sgt[pos].ls,le,mid,rb);

	else

	{

		int tmp = query(sgt[pos].rs,mid+1,ri,rb);

		return tmp ? tmp : query(sgt[pos].ls,le,mid,rb);

	}

}

int main()

{

	scanf("%s",a+1); n = strlen(a+1);

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

	sam.init();

	rtn = siz = 1;

	for(int i=1; i<=n; i++)

	{

		int u = sam.insertchar(a[i]);

		rt[u] = rtn; addval(rt[u],1,n,i);

	}

	sam.getord();

	for(int i=sam.siz; i>=1; i--)

	{

		int u = sam.ord[i];

		rt[sam.fa[u]] = merge(rt[sam.fa[u]],rt[u]);

	}

	scanf("%d",&q);

	while(q--)

	{

		for(int i=1; i<=samt.siz; i++) mxl[i] = 0;

		samt.init();

		scanf("%s",b+1); m = strlen(b+1); int lb,rb; scanf("%d%d",&lb,&rb);

		for(int i=1; i<=m; i++) b[i]-=96;

		for(int i=1; i<=m; i++) samt.insertchar(b[i]);

		samt.getord();

		int u = sam.rtn,uu = samt.rtn,cur = 0; llong ans = 0ll;

		for(int i=1; i<=m; i++)

		{

			while(u && sam.son[u][b[i]]==0) {u = sam.fa[u]; cur = sam.len[u];}

			if(u!=0) {u = sam.son[u][b[i]]; cur++;} else {u = sam.rtn; cur = 0;}

			int tmp = query(rt[u],1,n,rb);

			while(u && tmp<lb+sam.len[sam.fa[u]]) {u = sam.fa[u]; tmp = query(rt[u],1,n,rb); cur = min(sam.len[u],tmp-lb+1);}

			cur = min(cur,tmp-lb+1); //注意此处必须受到区间限制

			while(uu && samt.son[uu][b[i]]==0) {uu = samt.fa[uu];}

			uu = uu==0 ? 1 : samt.son[uu][b[i]];

			mxl[uu] = max(mxl[uu],cur);

		}

		for(int i=samt.siz; i>=1; i--)

		{

			int uu = samt.ord[i];

			mxl[samt.fa[uu]] = max(mxl[samt.fa[uu]],mxl[uu]);

		}

		for(int i=1; i<=samt.siz; i++)

		{

			mxl[i] = max(min(mxl[i],samt.len[i]),samt.len[samt.fa[i]]); //最长匹配的长度，不得小于该点最短长度

			int tmp = samt.len[i]-mxl[i]; //该节点上不匹配的个数

			ans += (llong)tmp;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

UOJ #395 BZOJ 5417 Luogu P4770 [NOI2018]你的名字 (后缀自动机、线段树合并)

代码

最新文章

热门文章