简要题意

给出一个长度为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;
}