簡要題意
給出一個長度為n的字符串s[1]，由小寫字母組成。定義一個字符串序列s[1....k],滿足性質：s[i]在s[i-1] (i>=2)中出現至少兩次（位置可重疊），問最大的k是多少，使得從s[1]開始到s[k]都滿足這樣一個性質。
\(n\le 200000\)
Sol
一道適合練習SAM的right集合神題 + 神仙結論題
結論（1）
每次只算\(s[i-1]\)是\(s[i]\)的后綴的情況，顯然是不會影響答案的。
因為如果\(s[i-1]\)不是\(s[i]\)的后綴，那么我們把不與\(s[i-1]\)匹配的那后面一截都去掉，\(s[i]\)就會變短。
如果沒變短之前它在某一個字符串里出現過了，那么變短后顯然還是出現過的。
這個結論是顯然的，也比結論（2）容易理解。
建立后綴自動機。
容易想到直接在parent樹上自上向下DP；
考慮如何判斷x的祖先y所代表的子串是否在x中出現了兩次：
\(len[x]\)表示\(x\)代表的最長子串長度，假設\(x\)的\(right\)集合中存在一個位置\(p\)，
那么\(p\)顯然已經在\(y\)的\(right\)集合中了，
我們只要判斷\(y\)的\(right\)集合中有沒有一個元素，
在區間\([pos(x)-len(x)+len(y),pos(x)-1]\)中判斷y串是否出現兩次即可。
這個容易線段樹合并完成。
可以發現，我們以上的做法都只考慮父親代表的最長串都必須出現在x代表的最長串中。
這樣有沒有問題呢？又如何dp呢？
結論（2）
設s是某個節點u表示的最長串,v是u的祖先（即串的后綴），
則v表示的所有字符串在s上的匹配情況是等價的（即不會出現有的能匹配、有的不能）。
證明的話，我們舉個例子：
\((1)\ \ \ \ \ \ abcb\)
\((2)\ \ \ \ babcb\)
\((s)\ \ \ \ \ \ abcbabcb\)
考慮反證：
假設這里(s)的后綴(1)(2)均為v節點表示的串，（1）成功匹配而（2）不行。
因為(2)，所有顯然還存在著這個串：
\((3)\ \ \ \ babcbabcb\)
又因為(s)表示的已經是u的最長串了，所以(3)串一定來自另一個節點。
設(3)串來自另一個節點w，u是w的祖先。
根據定義知
\[ |Right(u)| > |Right(w)| \]
這樣，則一定存在一個位置p
\[p ∈Right(u) - Right(w)\]
在這個位置只出現了(s)串而沒有(3)串。
這樣就存在一個位置使得只出現(1)串而沒有(2)串。
這樣得到(1)(2)兩串\(Right\)集合不同？？
這與它們來自同一個節點矛盾！
證畢.
有了結論（2），我們就可以設計dp狀態了：
\(dp[i]\)表示使用節點i最長的那個字符串的答案，
轉移的時候可以直接使用祖先節點j最長的那個字符串轉移（因為都等價啊）
這樣一來整個dp過程都是忽略那部分短串的，就非常自然了。
這個dp顯然可以倍增，容易做到線性（對深度Two-pointer）。
#include<set>
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;const int N=400005;char S[N];
int n,tot(1),la,ch[N][26],len[N],fa[N],pos[N],rt[N],cnt,rk[N],ar[N],dp[N],fr[N],Ans;struct node {int lc,rc;
}t[N*20];void Upd(int &u,int l,int r,int p)
{if(!u)u=++cnt;if(l!=r){int m=(l+r)>>1;if(m>=p) Upd(t[u].lc,l,m,p);else Upd(t[u].rc,m+1,r,p);}
}int Merge(int x,int y,int l,int r)
{if(!x||!y)return x+y;int o=++cnt;if(l!=r){int m=(l+r)>>1;t[o].lc=Merge(t[x].lc,t[y].lc,l,m);t[o].rc=Merge(t[x].rc,t[y].rc,m+1,r);}return o;
}int Query(int u,int l,int r,int L,int R)
{if(!u||l>R||r<L)return 0;if(l>=L&&r<=R)return 1;int m=(l+r)>>1;return Query(t[u].lc,l,m,L,R)||Query(t[u].rc,m+1,r,L,R);
}void extend(int id,int where)
{int p=la;int np=++tot;len[np]=len[p]+1;pos[np]=where;while(p && !ch[p][id]){ch[p][id]=np;p=fa[p];}if(!p){fa[np]=1;}else{int q=ch[p][id];if(len[p]+1==len[q]){fa[np]=q;}else{int nq=++tot;len[nq]=len[p]+1;fa[nq]=fa[q];pos[nq]=pos[q];for(int i=0; i<26; i++)ch[nq][i]=ch[q][i];fa[np]=fa[q]=nq;while(p && ch[p][id]==q){ch[p][id]=nq;p=fa[p];}}}la=np;Upd(rt[la],1,n,where);
}void Sort()
{for(int i=1; i<=tot; i++) ar[len[i]]++;for(int i=1; i<=n; i++) ar[i]+=ar[i-1];for(int i=1; i<=tot; i++) rk[ar[len[i]]--]=i;
}int main()
{scanf("%d%s",&n,S+1);la=1;for(int i=1; i<=n; i++) extend(S[i]-'a',i);Sort();for(int i=tot; i!=1; i--){int u=rk[i],v=fa[u];rt[v]=Merge(rt[v],rt[u],1,n);}for(int i=2; i<=tot; i++){int u=rk[i],v=fa[u];if(v==1){dp[u]=1;fr[u]=u;}else if(Query(rt[fr[v]],1,n,pos[u]-len[u]+len[fr[v]],pos[u]-1)){dp[u]=dp[v]+1;fr[u]=u;}else{dp[u]=dp[v];fr[u]=fr[v];}Ans=max(Ans,dp[u]);}printf("%d",Ans);return 0;
}
 return code = -2...)
