【BZOJ5496】[十二省联考2019]字符串问题（后缀树）

时间：2023-03-09 09:35:10
【BZOJ5496】[十二省联考2019]字符串问题（后缀树）

【BZOJ5496】[十二省联考2019]字符串问题（后缀树）

题面

BZOJ

洛谷

题解

首先显然可以把具有支配关系的串从\(A\)到\(B\)连一条有向边，如果\(B_i\)是\(A_j\)的前缀，就从\(B\)连一条边到\(A\)。这样子问题就转化成了要求解这个二分图的最长路经，有环答案就是\(-1\)。

然后显然就是要找个什么东西出来优化连边是吧。。。

现在唯一要处理的东西就是要找到个啥玩意，来优化这个满足前缀条件的连边。

假装我们有一个所有后缀都被插进去的\(Trie\)树，那么对于每一个\(B\)只需要找到其对应的节点，然后它子树中的每一个\(A\)都会被他连过去，这样子似乎就达成了优化连边，即每一个\(B\)连向这个节点，然后这样节点连向在这个节点终止的\(A\)。

这个复杂度显然是爆炸的，所以我们可以直接建立后缀树，这样子节点数就被优化到了\(O(n)\)级别。

于是问题又出现了，在后缀树上的一个节点表示的长度是一段区间，假如一个节点上又挂了\(A\)，又挂了\(B\)就会出锅。（虽然不管这个也有\(80\)分了）

那行啊，我们来拆个点，每个树上节点拆两个，一个\(u\)负责挂好所有儿子，另外一个\(v\)负责挂好所有在这个点的\(A\)，然后所有的\(A\)按照长度从小往大挂成一条链。然后\(v\)指向\(u\)，这样子任何一个\(B\)对应的一定是一段后缀\(A\)，所以直接后缀优化连边连向这条链，然后再连向\(u\)表示指向所有的儿子。

这样子还是很麻烦，实际上有一个更加优秀的做法，就是对于一个点如果挂了多个串，那么就按照每个串长把这个点强行拆掉就行了（虽然本质上就是挂了一条链）。

于是只需要求解最长路就行了，而且还是树上的最长链，只需要按照拓扑序做就行了，即使有环也可以在这个过程中处理掉。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 800800

#define pb push_back

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

vector<int> E[MAX],W[MAX],str[MAX];

char ch[MAX];int Len;

int fa[20][MAX],pos[MAX],val[MAX];

struct Node{int son[26],len,ff;void clear(){memset(son,0,sizeof(son));len=ff=0;}}t[MAX];

int last=1,tot=1;

void extend(int c)

{

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

	t[np].len=t[p].len+1;

	while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;

	if(!p)t[np].ff=1;

	else

	{

		int q=t[p].son[c];

		if(t[q].len==t[p].len+1)t[np].ff=q;

		else

		{

			int nq=++tot;

			t[nq]=t[q];t[nq].len=t[p].len+1;

			t[q].ff=t[np].ff=nq;

			while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;

		}

	}

}

vector<int> ee[MAX];

void dfs(int u,int ff)

{

	fa[0][u]=ff;

	for(int i=1;i<20;++i)fa[i][u]=fa[i-1][fa[i-1][u]];

	for(int i=0,l=ee[u].size();i<l;++i)dfs(ee[u][i],u);

}

void Work()

{

	Len=strlen(ch+1);

	for(int i=Len;i;--i)extend(ch[i]-97),pos[i]=last;

	for(int i=1;i<=tot;++i)ee[t[i].ff].pb(i);

	dfs(1,0);

}

int TOT,nd[MAX],IDA[MAX],IDB[MAX],Lim[MAX],lenA[MAX];

void Add(int u,int v,int w){if(u)E[u].pb(v),W[u].pb(w);}

bool cmp(int a,int b){return lenA[a]<lenA[b];}

void Build(int u,int ff)

{

	int np=++TOT;nd[u]=np;Lim[np]=t[u].len;

	if(ff)

	{

		int lst=ff;

		for(int i=0,l=str[u].size();i<l;++i)

		{

			Add(lst,++TOT,0),val[TOT]=lenA[str[u][i]],fa[0][TOT]=lst,Lim[TOT]=lenA[str[u][i]],lst=TOT;

			IDA[str[u][i]]=TOT;

		}

		Add(lst,np,0);fa[0][np]=lst;

	}

	for(int i=0,l=ee[u].size();i<l;++i)Build(ee[u][i],np);

}

int deg[MAX];ll dis[MAX],ans;

void Topsort()

{

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

		for(int j=0,l=E[i].size();j<l;++j)

			deg[E[i][j]]+=1;

	queue<int> Q;int QwQ=0;

	for(int i=1;i<=TOT;++i)if(!deg[i])Q.push(i);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();QwQ+=1;

		ans=max(ans,dis[u]+val[u]);

		for(int i=0,l=E[u].size();i<l;++i)

		{

			int v=E[u][i];

			dis[v]=max(dis[v],dis[u]+W[u][i]);

			if(!--deg[v])Q.push(v);

		}

	}

	if(QwQ<TOT)puts("-1");

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

}

int main()

{

	int T=read();

	while(T--)

	{

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

		Work();

		int A=read();

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

		{

			int l=read(),r=read(),len=r-l+1;

			int u=pos[l];lenA[i]=len;

			for(int i=19;~i;--i)

				if(t[fa[i][u]].len>=len)u=fa[i][u];

			str[u].pb(i);

		}

		for(int i=1;i<=tot;++i)sort(str[i].begin(),str[i].end(),cmp);

		for(int i=0;i<=tot;++i)

			for(int j=0;j<20;++j)fa[j][i]=0;

		Build(1,0);

		for(int j=1;j<20;++j)

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

				fa[j][i]=fa[j-1][fa[j-1][i]];

		int B=read();

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

		{

			int l=read(),r=read(),len=r-l+1;IDB[i]=++TOT;

			int u=nd[pos[l]];

			for(int j=19;~j;--j)

				if(Lim[fa[j][u]]>=len)u=fa[j][u];

			Add(IDB[i],u,0);

		}

		int C=read();

		while(C--)

		{

			int x=read(),y=read();

			Add(IDA[x],IDB[y],lenA[x]);

		}

		Topsort();

		for(int i=0;i<=TOT;++i)

		{

			ee[i].clear();E[i].clear();t[i].clear();

			str[i].clear();W[i].clear();

			for(int j=0;j<20;++j)fa[j][i]=0;

			IDA[i]=IDB[i]=Lim[i]=pos[i]=deg[i]=0;

			dis[i]=ans=val[i]=lenA[i]=nd[i]=0;

		}

		last=tot=1;TOT=0;

	}

	return 0;

}

相关文章