好神仙的一道字符串题！
由于后缀自动机+线段树合并的题做多了，看到复杂字符串的时候直接往 right 集合和后缀树那方面想了.
所以就没想出来 QAQ....
这道题还是要从序列上来思考.
我们发现最优解一定可以表示成一个长度依次为 $1$ ~ $ans$ 字符串集合.
- 令 $dp[i]$ 表示以 $i$ 开头的答案.
- 那么有 $dp[i] leqslant dp[i+1]+1$
- $dp[i]=dp[j]+1$，其中 $dp[j]$ 是最大满足可以转移的.
- 由 $dp[i] leqslant dp[i+1]+1$，我们可以直接枚举 $dp$ 值并验证.
- 验证的话需要满足 $i$ 开头的字符串是某个 $j$ 串的前缀或后缀.
- 由于满足 $dp[i] leqslant dp[j]+1$，所以当 $dp[i]$ 减小时可提供贡献的 $j$ 也相应减小，类加进来就行.
- 统计的话用一个倍增 + 线段树维护后缀树的 dfs 序即可.
code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000006
#define lson now<<1
#define rson now<<1|1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
int last=1,tot=1,tim,edges,n;
int f[21][N],ep[N],dp[N];
int hd[N],to[N],nex[N],maxv[N<<2];
int ch[N][26],pre[N],mx[N],pos[N],dfn[N];
void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void update(int l,int r,int now,int p,int v)
{
maxv[now]=max(maxv[now],v);
if(l==r)
return;
int mid=(l+r)>>1;
if(p<=mid)
update(l,mid,lson,p,v);
else
update(mid+1,r,rson,p,v);
}
int query(int l,int r,int now,int L,int R)
{
if(R<l||L>r||L>R)
return 0;
if(l>=L&&r<=R)
return maxv[now];
int mid=(l+r)>>1,re=0;
if(L<=mid)
re=max(re,query(l,mid,lson,L,R));
if(R>mid)
re=max(re,query(mid+1,r,rson,L,R));
return re;
}
void extend(int c,int id)
{
int np=++tot,p=last;
mx[np]=mx[p]+1,last=np;
for(;p&&!ch[p][c];p=pre[p])
ch[p][c]=np;
if(!p)
pre[np]=1;
else
{
int q=ch[p][c];
if(mx[q]==mx[p]+1)
pre[np]=q;
else
{
int nq=++tot;
mx[nq]=mx[p]+1;
pre[nq]=pre[q],pre[np]=pre[q]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
for(;p&&ch[p][c]==q;p=pre[p])
ch[p][c]=nq;
}
}
pos[id]=last;
}
void dfs(int x)
{
dfn[x]=++tim;
f[0][x]=pre[x];
for(int i=1;(1<<i)<=tot;++i)
f[i][x]=f[i-1][f[i-1][x]];
for(int i=hd[x];i;i=nex[i])
dfs(to[i]);
ep[x]=tim;
}
int get_p(int x,int d)
{
x=pos[x];
for(int i=20;i>=0;--i)
if(f[i][x]&&mx[f[i][x]]>=d)
x=f[i][x];
return x;
}
int check(int x,int d)
{
if(d==1)
return 1;
if(x-d+1<1)
return 0;
int p=get_p(x,d-1);
if(query(1,tot,1,dfn[p],ep[p])>=d-1)
return 1;
p=get_p(x-1,d-1);
if(query(1,tot,1,dfn[p],ep[p])>=d-1)
return 1;
return 0;
}
int main()
{
// setIO("input");
int i,j,ans=0;
scanf("%d%s",&n,str+1);
reverse(str+1,str+1+n);
for(i=1;i<=n;++i)
extend(str[i]-'a',i);
for(i=2;i<=tot;++i)
add(pre[i],i);
dfs(1);
for(i=1,j=0;i<=n;++i)
{
dp[i]=dp[i-1]+1;
while(!check(i,dp[i]))
{
--dp[i],++j;
update(1,tot,1,dfn[get_p(j,dp[j])],dp[j]);
}
ans=max(ans,dp[i]);
}
printf("%d
",ans);
return 0;
}