题解

首先我们注意到对于任意一种划分，我们都可以把它调整长度为\((len,len-1,len-2....1)\)的。所以我们可以用\((\tt{第一个串的位置，第一个串的长度})\)来表示一个划分。

所以我们可以设\(dp[i][j]\)表示\((i,j)\)这种方案是否可行，转移是从后往前的，可以用哈希，因为第二维是根号级别的，所以复杂度为\(n\sqrt{n}\)。

发现若有\(dp[i][j]\),那么就有\(dp[i][j-1]\)，我们可以换一种状态设计令\(dp[i]\)表示最大的合法的\(j\)。

若要判断\((i,j)\)是否合法，我们需要在\((i+j,n)\)中找到\(lcp(i,x)\geq j-1 ||lcp(i+1,x)\geq j-1\)，这个可以用后缀数组+主席树在\(logn\)的时间内判断。

这个东西可以二分，但是我们发现\(dp[i]\leq dp[i+1]+1\),于是我们的判断次数就变成\(O(n)\)的了。

代码

#include
    
     #define N 500009#define inf 1e9#define ls tr[cnt].l#define rs tr[cnt].rusing namespace std;typedef long long ll;char s[N];int n,tong[N],y[N],rnk[N],sa[N],dp[N],p[21][N],h[N],m,Log[N],tott,T[N];inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct seg{    int l,r,mx;}tr[N*21];int query(int cnt,int l,int r,int L,int R){    if(!cnt)return 0;    if(l>=L&&r<=R)return tr[cnt].mx;    int mid=(l+r)>>1,ans=0;    if(mid>=L)ans=max(ans,query(ls,l,mid,L,R));    if(mid
     
      >1;    if(mid>=x)upd(ls,tr[pre].l,l,mid,x,y);    else upd(rs,tr[pre].r,mid+1,r,x,y);    tr[cnt].mx=max(tr[ls].mx,tr[rs].mx);}inline int lcp(int l,int r){    if(l>r)swap(l,r);    if(l==r)return inf;    l++;    int lo=Log[r-l+1];    return min(p[lo][l],p[lo][r-(1<
      
       =1;--i)sa[tong[rnk[y[i]]]--]=y[i];}inline void SA(){    m=200;    for(int i=1;i<=n;++i)rnk[i]=s[i],y[i]=i;    qsort();    for(int w=1,p=0;p
       
        <<=1,m=p){        p=0;        for(int i=n-w+1;i<=n;++i)y[++p]=i;        for(int i=1;i<=n;++i)if(sa[i]>w)y[++p]=sa[i]-w;        qsort();        swap(rnk,y);        rnk[sa[1]]=p=1;        for(int i=2;i<=n;++i)            rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;    }    for(int i=1;i<=n;++i){        if(rnk[i]==1)continue;        int y=max(0,h[rnk[i-1]]-1);        while(s[i+y]==s[sa[rnk[i]-1]+y])y++;        h[rnk[i]]=p[0][rnk[i]]=y;    }    for(int i=1;(1<
        
         <=n;++i)        for(int j=1;j+(1<
         
          <=n;++j) p[i][j]=min(p[i-1][j],p[i-1][j+(1<
          
           >1; if(lcp(rnk[x],mid)>=len-1)ansr=mid,l=mid+1; else r=mid-1; } l=1;r=rnk[x]; int ansl=n+1; while(l<=r){ int mid=(l+r)>>1; if(lcp(mid,rnk[x])>=len-1)ansl=mid,r=mid-1; else l=mid+1; } if(ansl<=ansr)if(query(T[x+len],1,n,ansl,ansr)>=len-1)return 1; x++; l=rnk[x],r=n,ansr=0; while(l<=r){ int mid=(l+r)>>1; if(lcp(rnk[x],mid)>=len-1)ansr=mid,l=mid+1; else r=mid-1; } l=1;r=rnk[x]; ansl=n+1; while(l<=r){ int mid=(l+r)>>1; if(lcp(mid,rnk[x])>=len-1)ansl=mid,r=mid-1; else l=mid+1; } if(ansl<=ansr)if(query(T[x+len-1],1,n,ansl,ansr)>=len-1)return 1; return 0;}int main(){ n=rd(); scanf("%s",s+1); for(int i=2;i<=n;++i)Log[i]=Log[i>>1]+1; SA(); int ans=0; for(int i=n;i>=1;--i){ int mx=dp[i+1]+1; while(!pd(i,mx))mx--; dp[i]=mx; upd(T[i],T[i+1],1,n,rnk[i],mx); ans=max(ans,dp[i]); } cout<