Codeforces 700E. Cool Slogans 字符串,SAM,线段树合并,动态规划

原文链接https://www.cnblogs.com/zhouzhendong/p/CF700E.html

题解

首先建个SAM。

一个结论：对于parent树上任意一个点x，以及它所代表的子树内任意一个点y，设节点y代表的最长串为S，设节点x代表的串为T1,T2,T3,...，设 F(S,T) 表示串T在S中的出现次数，则 F(S,T1) = F(S,T2) = F(S,T3) = ...

证明：假设串 Ta 和 Tb 在 S 中的出现次数不同，且 |Ta|+1=|Tb| 则必然存在一个位置，使得将 Tb 放在这里的时候，它的最左端点不和 S 匹配，其他位置都匹配，这样的话，Tb 的 Right 集合至少比 Ta 多这个位置，与 “Ta,Tb 都是节点 x 代表的串” 矛盾。故原命题得证。

第二个结论：一定存在一个最优解，使得 $\forall 1<i\leq k$， $S_{i-1}$ 是 $S_i$ 的 Border 。

这个很好证，如果不是 Border ，把 $S_i$ 两边多出来的割掉一定不亏。

于是我们可以开始规划算法了。

设 $dp[S]$ 表示每次保证前一个串在后一个串中出现至少 2 次，从空串转移到串 $S$ 的最多转移次数。

我们把状态用 parent 树上的节点表示，由于第一个结论，对于每一个节点，我们可以只把这个节点代表的最长串作为有效状态；转移的时候，只要看看父亲的串在当前节点的串中出现次数是否至少2次，如果不到，就直接继承父亲的结果，否则更新为当前结果； 判断出现多少次需要处理出 Right 集合，线段树合并即可。

代码

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof (x))

using namespace std;

typedef long long LL;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=200005*2;

int n;

namespace seg{

	const int S=N*50;

	int ls[S],rs[S],size[S],cnt,root;

	void Init(){

		cnt=root=0;

		clr(ls),clr(rs),clr(size);

	}

	void Ins(int &rt,int L,int R,int x){

		if (!rt)

			rt=++cnt;

		size[rt]++;

		if (L==R)

			return;

		int mid=(L+R)>>1;

		if (x<=mid)

			Ins(ls[rt],L,mid,x);

		else

			Ins(rs[rt],mid+1,R,x);

	}

	int Merge(int a,int b,int L,int R){

		if (!a||!b)

			return a+b;

		int rt=++cnt;

		if (L==R)

			size[rt]=1;

		else {

			int mid=(L+R)>>1;

			ls[rt]=Merge(ls[a],ls[b],L,mid);

			rs[rt]=Merge(rs[a],rs[b],mid+1,R);

			size[rt]=size[ls[rt]]+size[rs[rt]];

		}

		return rt;

	}

	int Query(int rt,int L,int R,int xL,int xR){

		if (!rt||xL>R||L>xR)

			return 0;

		if (xL<=L&&R<=xR)

			return size[rt];

		int mid=(L+R)>>1;

		return Query(ls[rt],L,mid,xL,xR)

			  +Query(rs[rt],mid+1,R,xL,xR);

	}

}

namespace SAM{

	int last,size,root;

	struct Node{

		int Next[26],fa,Max,pos;

	}t[N];

	int Init(){

		clr(t);

		return last=size=root=1;

	}

	void extend(int c,int ps){

		int p=last,np=++size,q,nq;

		t[np].Max=t[p].Max+1,t[np].pos=ps;

		for (;p&&!t[p].Next[c];p=t[p].fa)

			t[p].Next[c]=np;

		if (!p)

			t[np].fa=root;

		else {

			q=t[p].Next[c];

			if (t[p].Max+1==t[q].Max)

				t[np].fa=q;

			else {

				nq=++size;

				t[nq]=t[q],t[nq].Max=t[p].Max+1,t[nq].pos=ps;

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

				for (;p&&t[p].Next[c]==q;p=t[p].fa)

					t[p].Next[c]=nq;

			}

		}

		last=np;

	}

	int id[N],tax[N],rt[N];

	void sort(){

		clr(tax);

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

			tax[t[i].Max]++;

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

			tax[i]+=tax[i-1];

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

			id[tax[t[i].Max]--]=i;

	}

	void build(){

		sort();

		seg::Init();

		for (int i=size;i>1;i--)

			seg::Ins(rt[id[i]],1,n,t[id[i]].pos);

		for (int i=size;i>1;i--){

			int x=id[i],f=t[x].fa;

			rt[f]=seg::Merge(rt[f],rt[x],1,n);

		}

	}

	int dp[N],nid[N];

	int Horse_NMDP(){

		int ans=0;

		dp[1]=0,nid[1]=1;

		for (int i=2;i<=size;i++){

			int x=id[i],f=nid[t[x].fa];

			if (f==1||seg::Query(rt[f],1,n,t[x].pos-t[x].Max+t[f].Max

										  ,t[x].pos)>=2)

				dp[x]=dp[f]+1,nid[x]=x;

			else

				dp[x]=dp[f],nid[x]=f;

			ans=max(ans,dp[x]);

		}

		return ans;

	}

}

using SAM::t;

using SAM::extend;

char s[N];

int main(){

	n=read();

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

	SAM::Init();

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

		extend(s[i]-'a',i);

	SAM::build();

	cout<<SAM::Horse_NMDP()<<endl;

	return 0;

}