题解-CodeForces700E Cool Slogans

时间:2022-03-23 17:29:29

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;
}