https://codeforces.com/contest/700/problem/E
题解：https://www.luogu.org/problemnew/solution/CF700E
其实就是从父亲到儿子dp，因为parent树上父亲一定是儿子的后缀，那么只要再找一个出现位置就好了，又因为父亲的right集合包含儿子的right集合，所以对于任意一个儿子出现的位置check就好。然后开n颗动态开点线段树按照拓扑序从下网上合并一下搞出每个点的right集合，然check一下f[fa]这颗树在(pos[son]-len[son]+len[fa],pos[son]-1)有没有值就好了，因为pos[son]已经出现过一个。代码写得和yyb太像了QAQ ,merge写得不对QAQ。extend 和insertt不要都用cnt去开点，不然RE很无情。
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=5e5+100;
char s[maxn];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct str
{
int son[26];
int ff,len,pos;
}sr[maxn];
struct node
{
int l,r;
}no[maxn*80];
int cnt=1,last=1,tot;
int c[maxn],a[maxn],siz[maxn];
int rt[maxn];
int n;
int ans[maxn],f[maxn];
void insertt(int &x,int l,int r,int pl)
{
if(!x)x=++tot;
if(l==r)return;
int mid=(l+r)>>1;
if(pl<=mid)insertt(no[x].l,l,mid,pl);
else insertt(no[x].r,mid+1,r,pl);
}
int merge(int x,int y)
{
if(!x||!y){return x|y;}
int z=++tot;
no[z].l=merge(no[x].l,no[y].l);
no[z].r=merge(no[x].r,no[y].r);
return z;
}
void extend(int c,int pos)
{
int p=last,np=++cnt;last=np;
sr[np].len=sr[p].len+1;sr[np].pos=pos;
while(p&&!sr[p].son[c])sr[p].son[c]=np,p=sr[p].ff;
if(!p)sr[np].ff=1;
else
{
int q=sr[p].son[c];
if(sr[p].len+1==sr[q].len)sr[np].ff=q;
else
{
int nq=++cnt;
sr[nq]=sr[q];
sr[nq].len=sr[p].len+1;
sr[q].ff=sr[np].ff=nq;
while(p&&sr[p].son[c]==q)sr[p].son[c]=nq,p=sr[p].ff;
}
}
siz[np]=1;
}
int query(int x,int l,int r,int L,int R)
{
if(!x)return 0; if(L<=l&&r<=R)return 1;
int mid=(l+r)>>1;
if(L<=mid){if(query(no[x].l,l,mid,L,R))return 1;}
if(R>mid){if(query(no[x].r,mid+1,r,L,R))return 1;}
return 0;
}
int res=1;
int main()
{
n=read();
scanf("%s",s+1);
//memset(sr,0,sizeof(sr));
cnt=1;last=1;
for(int i=1;i<=n;i++)extend(s[i]-'a',i),insertt(rt[last],1,n,i);
for(int i=1;i<=cnt;i++)c[sr[i].len]++;
for(int i=1;i<=n;i++)c[i]+=c[i-1];
for(int i=1;i<=cnt;i++)a[c[sr[i].len]--]=i;
for(int i=cnt;i;i--)rt[sr[a[i]].ff]=merge(rt[sr[a[i]].ff],rt[a[i]]);
for(int i=2;i<=cnt;i++)
{
int tt=a[i],fa=sr[tt].ff;
if(fa==1){f[tt]=tt;ans[tt]=1;continue;}
int flag=query(rt[f[fa]],1,n,sr[tt].pos-sr[tt].len+sr[f[fa]].len,sr[tt].pos-1);
if(flag)ans[tt]=ans[fa]+1,f[tt]=tt;
else ans[tt]=ans[fa],f[tt]=f[fa];
res=max(res,ans[tt]);
}
cout<<res<<"
";
}