BZOJ.5417.[NOI2018]你的名字(后缀自动机线段树合并)

LOJ

洛谷

 BZOJ

考虑\(l=1,r=|S|\)的情况：

对\(S\)串建SAM，\(T\)在上面匹配，可以得到每个位置\(i\)的后缀的最长匹配长度\(mx[i]\)。

因为要去重，对\(T\)也建SAM，计算上面所有节点的答案。记\(pos[i]\)表示\(i\)节点第一次出现的下标（同一节点代表的串出现的位置集合相同，所以随便记一个即可）。

则节点\(i\)的答案为：\(\max(0,\ len[i]-\max(len[fa[i]],\ mx[pos[i]]))\)。

考虑\(l,r\)任意的情况：

要判断\(T\)能否在\(S[l,r]\)上匹配，也就是匹配的时候只能走在\(S[l,r]\)出现过的节点。

线段树合并，自底向上合并right集合，就可以得到SAM上每个节点出现过的位置（right）。

如果已匹配长度为\(now\)，那么区间查的时候要查\([l+now,r]\)啊（跳\(fa\)时要同时改\(now\)）（要不还是68分）。

而且\(now\)应该是每次减一，而不是令\(p\)直接跳\(fa\)（但还是有96分）。

好像只要还记得SAM的套路就没那么难？（反正我已经忘了）

明年还出SAM就好了。

/*

LOJ:10770ms	337788K

洛谷:16362ms	348.41MB

BZOJ:408052kb	28352ms

*/

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

const int N=1e6+5;

int mx[N],root[N];

char s[N];

struct Segment_Tree

{

	#define ls son[x][0]

	#define rs son[x][1]

	#define lson ls,l,m

	#define rson rs,m+1,r

	#define S N*20

	int tot,son[S][2];

	#undef S

	void Insert(int &x,int l,int r,int p)

	{

		/*if(!x)*/ x=++tot;//

		if(l==r) return;

		int m=l+r>>1;

		p<=m ? Insert(lson,p) : Insert(rson,p);

	}

	int Merge(int x,int y)

	{

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

		int now=++tot;

		son[now][0]=Merge(ls,son[y][0]), son[now][1]=Merge(rs,son[y][1]);

		return now;

	}

	bool Query(int x,int l,int r,int L,int R)

	{

		if(!x) return 0;

		if(L<=l && r<=R) return 1;

		int m=l+r>>1;

		if(L<=m)

			if(m<R) return Query(lson,L,R)||Query(rson,L,R);

			else return Query(lson,L,R);

		return Query(rson,L,R);

	}

	#undef ls

	#undef rs

}Tr;

struct Suffix_Automaton

{

	int n,tot,las,fa[N],son[N][26],len[N],tm[N],A[N],pos[N];

	void Insert(int c,int id)

	{

		int np=++tot,p=las;

		len[las=np]=len[p]+1, pos[np]=id;

		for(;p&&!son[p][c]; p=fa[p]) son[p][c]=np;

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

		else

		{

			int q=son[p][c];

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

			else

			{

				int nq=++tot;

				len[nq]=len[p]+1, pos[nq]=pos[q];

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

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

				for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;

			}

		}

	}

	void Build_S(char *s,int l)

	{

		memset(son,0,(tot+2)*sizeof son[0]);

		tot=las=1, n=l;

		for(int i=1; i<=n; ++i) Insert(s[i]-'a',i),Tr.Insert(root[las],1,n,i);

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

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

		for(int i=1; i<=tot; ++i) A[tm[len[i]]--]=i;

		for(int i=tot,x=A[i]; i>1; x=A[--i]) root[fa[x]]=Tr.Merge(root[x],root[fa[x]]);

	}

	void Build_T(char *s,int l)

	{

		memset(son,0,(tot+2)*sizeof son[0]);

		tot=las=1, n=l;

		for(int i=1; i<=l; ++i) Insert(s[i]-'a',i);

	}

}S,T;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

void Solve(int ls)

{

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

	int l=read(),r=read(),n=strlen(s+1);

	T.Build_T(s,n);

	for(int i=1,now=0,p=1,c; i<=n; mx[i++]=now)

	{

		c=s[i]-'a';

		while(1)

		{

			if(!Tr.Query(root[S.son[p][c]],1,ls,l+now,r))

			{

				if(!now) break;//匹配长度为0了要再匹配一次

				--now;

				if(now==S.len[S.fa[p]]) p=S.fa[p];

			}

			else {++now, p=S.son[p][c]; break;}

		}

//		if(Tr.Query(root[S.son[p][c]],1,ls,l+now,r)) p=S.son[p][c], ++now;

//		else

//		{

//			for(; p&&!Tr.Query(root[S.son[p][c]],1,ls,l+now,r); p=S.fa[p],now=S.len[p]);

//			if(!p) p=1, now=0;

//			else now=S.len[p]+1, p=S.son[p][c];//这样写96分 还只错了一个询问

//		}

	}

	LL ans=0;

	for(int i=2; i<=T.tot; ++i)

		ans+=std::max(0,T.len[i]-std::max(T.len[T.fa[i]],mx[T.pos[i]]));

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

}

int main()

{

//	freopen("name.in","r",stdin);

//	freopen("name.out","w",stdout);

	scanf("%s",s+1); int ls=strlen(s+1);

	S.Build_S(s,ls);

	for(int Q=read(); Q--; Solve(ls));

	return 0;

}

68分代码：

/*

对S串建SAM，T在上面匹配，可以得到每个位置i的后缀的最长匹配长度mx[i]。

因为要去重，对T也建SAM，计算上面所有节点的答案。记pos[i]表示i节点第一次出现的下标（同一节点代表的串出现的位置集合相同）。

则节点i的答案为：max(0, len[i]-max(len[fa[i]], mx[pos[i]]))。

*/

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

const int N=1e6+5;

int mx[N];

char s[N];

struct Suffix_Automaton

{

	int n,tot,las,fa[N],son[N][26],len[N],pos[N];

	void Insert(int c,int id)

	{

		int np=++tot,p=las;

		len[las=np]=len[p]+1, pos[np]=id;

		for(;p&&!son[p][c]; p=fa[p]) son[p][c]=np;

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

		else

		{

			int q=son[p][c];

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

			else

			{

				int nq=++tot;

				len[nq]=len[p]+1, pos[nq]=pos[q];

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

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

				for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;

			}

		}

	}

	void Build(char *s,int l)

	{

		memset(son,0,(tot+2)*sizeof son[0]);

		tot=las=1, n=l;

		for(int i=1; i<=n; ++i) Insert(s[i]-'a',i);

	}

}S,T;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

void Solve()

{

	int n=strlen(s+1);

	for(int i=1,now=0,p=1,c; i<=n; mx[i++]=now)

	{

		if(S.son[p][c=s[i]-'a']) p=S.son[p][c], ++now;

		else

		{

			for(; p&&!S.son[p][c]; p=S.fa[p]);

			if(!p) p=1, now=0;

			else now=S.len[p]+1, p=S.son[p][c];

		}

	}

	LL ans=0;

	for(int i=2; i<=T.tot; ++i)

		ans+=std::max(0,T.len[i]-std::max(T.len[T.fa[i]],mx[T.pos[i]]));

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

}

int main()

{

	freopen("name.in","r",stdin);

	freopen("name.out","w",stdout);

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

	S.Build(s,strlen(s+1)); int Q=read();

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

	{

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

		int l=read(),r=read();

		T.Build(s,strlen(s+1)), Solve();

	}

	return 0;

}

巴特西

BZOJ.5417.[NOI2018]你的名字(后缀自动机线段树合并)

最新文章

热门文章

巴特西

BZOJ.5417.[NOI2018]你的名字(后缀自动机 线段树合并)

最新文章

热门文章

BZOJ.5417.[NOI2018]你的名字(后缀自动机线段树合并)