服了，做这道题还要重新学一遍$SAM$，泪目了。

先不考虑复杂度，考虑一段子串$[i,j]$对应的答案。尽量将问题往$SAM$上去靠，发现子串$[i,j]$对应的就是从$t_0$出发的一条链。假设转移过去的子串是$[i^{\prime },j^{\prime }]$，如果$j^{\prime }=j$那么转移到的点一定是后缀树上的祖先节点，总之这个转移可以提前预处理出来。如果$j^{\prime }\ne j$那么相当于就是在链上取$\max$。又因为$SAM$的节点个数是线性的所以直接$DP$，这道题就做完了。

这是我做这道题的第一想法，但是其实我们可以再冷静的分析一步。先不考虑交叉的情况，简单画一个图可以发现最优方案中$s_{i-1}$一定是$s_i$的后缀。这样我们就不用管建出来的$DAG$，只需要考虑后缀树上的情形了，因为后缀树对应后缀链接。

比较让人纠结的地方在于，同一等价类对应的答案相同吗？这就涉及到我们对$SAM$基本性质的了解了。抛出一个结论：设$s$是节点$u$对应的最长串，$v$是$u$的祖先，那么$v$对应的所有字符串在$s$中的匹配情况相同。证明的关键在于利用$\text{endpos}$集合相同。感觉这个证明脑补一下应该不难就略过了。这也说明了一件事，对后缀性质的充分理解才是解决问题的关键。

最后是关于实现。直接暴力二分的复杂度是$O(n{\log }^{2}n)$。但是因为是在树上所以能做的操作还是比较多的，比如说这道题就可以根据父亲的信息来计算，注意到一条链上的$DP$值是连续的，并且相邻两个位置的$DP$值不超过$1$，因此可以做到线性。这个地方的处理还是比较巧妙的。复杂度$O(n\log n)$。

就是模板有点长。

打了一发代码，感觉最恶心的地方还是在于在$SAM$上维护一些比较繁琐的信息。如果对$SAM$不熟悉的话还是很容易搞错的。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
#define uint unsigned int
using namespace std;
const int N=4e5+5;
const int M=N*20;
int n,tot,last,rt[N],nums[N],cnt,degree[N],ls[M],rs[M],totnodes,dp[N],fr[N],res;
string s;
queue<int>Q;
struct node{int link,len,ch[26],pos;
}t[N];
void ins(int &rt,int l,int r,int x){if(!rt)rt=++totnodes;if(l==r)return;int mid=l+r>>1;x<=mid?ins(ls[rt],l,mid,x):ins(rs[rt],mid+1,r,x);
}
void extend(int c,int x){int cur=++tot;t[cur].len=t[last].len+1;t[cur].pos=x;int p=last;while(p!=-1&&!t[p].ch[c]){t[p].ch[c]=cur;p=t[p].link;}if(p==-1){t[cur].link=0;}else{//assert(t[p].ch[c]);int q=t[p].ch[c];assert(q);if(t[q].len==t[p].len+1){t[cur].link=q;}else{int clone=++tot;t[clone].link=t[q].link,t[clone].len=t[p].len+1;for(int i=0;i<26;i++)t[clone].ch[i]=t[q].ch[i];t[clone].pos=x;t[cur].link=clone;t[q].link=clone;while(p!=-1&&t[p].ch[c]==q){t[p].ch[c]=clone;p=t[p].link;} }}last=cur;ins(rt[cur],0,n-1,x);
}
int merge(int p,int q,int l,int r){if(l>r)return 0;if(!p||!q)return p+q;int o=++totnodes,mid=l+r>>1;ls[o]=merge(ls[p],ls[q],l,mid);rs[o]=merge(rs[p],rs[q],mid+1,r);return o;
}
int query(int p,int l,int r,int ql,int qr){if(!p)return 0;if(ql<=l&&r<=qr)return 1;int mid=l+r>>1;if(ql<=mid&&query(ls[p],l,mid,ql,qr))return 1;if(mid<qr&&query(rs[p],mid+1,r,ql,qr))return 1;return 0;
}
signed main(){//freopen("data.in","r",stdin);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>s;t[0].link=-1;for(int i=0;i<n;i++){extend(s[i]-'a',i);}for(int i=1;i<=tot;i++)degree[t[i].link]++;for(int i=1;i<=tot;i++){if(degree[i]==0){Q.push(i);}}while(Q.size()){int u=Q.front(),v=t[u].link;Q.pop();nums[++cnt]=u;if(v){rt[v]=merge(rt[v],rt[u],0,n-1);if(--degree[v]==0)Q.push(v);}}for(int i=1;i<=tot;i++)assert(degree[i]==0);assert(cnt==tot);for(int i=cnt;i>=1;i--){int x=nums[i],y=t[x].link;if(fr[y]==0||query(rt[fr[y]],0,n-1,t[x].pos-t[x].len+t[fr[y]].len,t[x].pos-1)){dp[x]=dp[fr[y]]+1;fr[x]=x;}else{dp[x]=dp[fr[y]];fr[x]=fr[y];}res=max(res,dp[x]);}cout<<res;
}