Problem

题目链接

题目大意：给定一个字符串，每次取出出现至少两次的子串替换原串，问最多能替换多少次，输出答案加一（字符串长为\(2×10^5\)）

Solution

前置技能：SAM、线段树合并、dp

首先可以想到一个dp（设t为在s中出现至少两次的子串）：\(dp[s]=\max\{dp[t] \}+1\)

然后想到如果t在s中出现不止一次，则在考虑t时，要求在s的endpos集合中一定存在一个处于区间\(\bigl[t_{longest}+s_{pos}-s_{longest},s_{longest}\bigr )\)的endpos，至于求endpos可以使用线段树合并求解

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rg register

const int N=401000,M=8001000;

int stp[N],ch[N][26],pre[N],pos[N],top[N],rt[N];

int ls[M],rs[M],b[N],f[N],tpy[N];

int n,tot=1,cnt,Ans=1,lst=1;

char s[N];

inline void ins(int x){

	int p=lst,np=++tot;

	lst=tot;stp[np]=stp[p]+1;

	while(p&&!ch[p][x])ch[p][x]=np,p=pre[p];

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

	else {

		int q=ch[p][x];

		if(stp[q]==stp[p]+1)pre[np]=q;

		else {

			int nq=++tot;stp[nq]=stp[p]+1;pos[nq]=pos[q];

			for(rg int i=0;i<26;++i)ch[nq][i]=ch[q][i];

			pre[nq]=pre[q];pre[q]=pre[np]=nq;

			while(ch[p][x]==q)ch[p][x]=nq,p=pre[p];

		}

	}return ;

}

inline int merge(int u,int v){

	if(!u||!v)return u+v;

	int z=++cnt;

	ls[z]=merge(ls[u],ls[v]);

	rs[z]=merge(rs[u],rs[v]);

	return z;

}

inline void update(int l,int r,int&x,int al){

	if(!x)x=++cnt;

	if(l==r)return ;

	int mid(l+r>>1);

	if(al<=mid)update(l,mid,ls[x],al);

	else update(mid+1,r,rs[x],al);

	return ;

}

inline int query(int l,int r,int x,int L,int R){

	if(!x)return 0;

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

	int mid(l+r>>1),res(0);

	if(L<=mid)if(query(l,mid,ls[x],L,R))return 1;

	if(mid<R)if(query(mid+1,r,rs[x],L,R))return 1;

	return 0;

}

int main(){

	scanf("%d%s",&n,s+1);

	for(rg int i=1;i<=n;++i){ins(s[i]-'a');update(1,n,rt[lst],i);pos[lst]=i;}

	for(rg int i=1;i<=tot;++i)++b[stp[i]];

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

	for(rg int i=tot;i;--i)tpy[b[stp[i]]--]=i;

	for(rg int i=tot;i^1;--i)rt[pre[tpy[i]]]=merge(rt[pre[tpy[i]]],rt[tpy[i]]);

	for(rg int i=2;i<=tot;++i){

		int x(tpy[i]),fa(pre[x]);

		if(fa==1){f[x]=1,top[x]=x;continue;}

		if(query(1,n,rt[top[fa]],pos[x]-(stp[x]-stp[top[fa]]),pos[x]-1))f[x]=f[fa]+1,top[x]=x;

		else f[x]=f[fa],top[x]=top[fa];

		Ans=max(Ans,f[x]);

	}printf("%d\n",Ans);return 0;

}