先 reverse 一下。
不难看出选出的字符串长度为 \(1,2,\cdots,k\) 一定不劣，仅考虑这种形式的。
然后考虑一手 dp，设 \(f_{i}\) 表示最后一个子串是 \(i\) 为结尾，最长长度是多少。
这样转移就是 \(f_i\gets f_{j}+1,iff\ s[j-f_j+1,j]\text { is } s[i-f_j,i] \text{'s substring}\)．
掏出了一个结论，\(f_{i+1}\leq f_i+1\)，因为不成立的话 \(f_i\) 一定可以调整得更大。
那么问题就可以从求解变成判定。具体就是初始时 \(i=k=1\)，判定 \(f_i\) 是否 \(\geq k\)，如果成功则 \(i,k\) 都 \(+1\)，否则只有 \(k\gets k-1\)，然后继续判定。总共判定 \(\mathcal{O}(n)\) 次。
那么现在问题就是判定 \([i-k+1,i]\) 能否选出，一种情况是上一个字符串 \(t\) 是 \(s[i-k+1,i-1]\)，另一种情况是 \(s[i-k+2,i]\)，注意到每次 \(i,k\) 同时 \(+1\) 相当于右端点向右一步；\(k\gets k-1\) 的时候相当于左端点向右一步。那么可以直接动态地维护这两个串在 SAM 上的位置，右端点向右一步就直接走自动机上的边，左端点向右一步就看看 \(len\) 是否还在当前节点的 \(len\) 范围中，如果不在就跳一步 parent 树上的父亲。
定位出这个节点之后，考虑需要判断是否存在上一个选出的串的右端点 \(j\)，其合法要满足 \(f_j\geq k-1\) 且 \(j\leq i-k\) 且 \(t\) 是 \(s[j-f_j+1,j]\) 的后缀．
注意到每次 \(i,k\) 变化时是同时 \(+1\) 或者 \(k\gets k-1\)，那么 \(i-k\) 是不降的。于是扫 \(i,k\) 的时候再每次把 \(f_{i-k}\) 给 SAM 上 \(s[i-k-f_{i-k}+1,i-k]\) 所代表的节点单点 \(\text{chkmax}\)，查询的时候就查 parent 子树 \(\max\)，就可以了。这样总的时间复杂度是 \(\mathcal{O}(n\log n)\)．
真的有必要这样吗？
仔细想一想，由于子树中的等价类 \(len\) 一定大于当前节点的 \(len\)，所以子树中一旦出现了一个单点 \(\text{chkmax}\)，那么自己肯定是合法的，所以只需要记录出每个点子树中（不包含自己）是否已经出现过点，记作 \(ok\)，并且记录每个点处的 \(f\) 的 \(\max\)，判断合法时直接判 \(f\geq k\) 或者 \(ok\) 已经是否已经被标记过即可。扫 \(i,k\) 的时候加入 \(f_{i-k}\) 时，暴力不断在 parent 树上跳 father 更新 \(ok\) 即可，如果之前已经跳到过了就不再跳了（一个点被标记那么其祖先已均被标记）。这样均摊下来总的时间复杂度是 \(\mathcal{O}(n)\)．
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#include<assert.h>
#include<functional>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
r=0;bool w=0;char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int mod=998244353;
inline void cadd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void cdel(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int del(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
int qpow(int x,int y){
int s=1;
while(y){
if(y&1)s=1ll*s*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return s;
}
const int N=500010;
struct Node{
int ch[26],len,fa;
}a[N<<1];
int tot=1,las=1;
void Ins(int x){
int cur=++tot;
int p=las;a[cur].len=a[las].len+1;las=cur;
for(;p&&!a[p].ch[x];p=a[p].fa)a[p].ch[x]=cur;
if(!p)a[cur].fa=1;
else{
int q=a[p].ch[x];
if(a[q].len==a[p].len+1)a[cur].fa=q;
else{
int c=++tot;a[c]=a[q];
a[c].len=a[p].len+1;
a[q].fa=a[cur].fa=c;
for(;p&&a[p].ch[x]==q;p=a[p].fa)a[p].ch[x]=c;
}
}
}
int n;
char s[N];
int f[N],g[N<<1],ok[N<<1],po[N];
signed main(){
#ifdef do_while_true
// assert(freopen("data.in","r",stdin));
// assert(freopen("data.out","w",stdout));
#endif
read(n);
scanf("%s",s+1);
reverse(s+1,s+n+1);
for(int i=1;i<=n;i++)Ins(s[i]-'a');
int lp=1,rp=1;
int now=a[1].ch[s[1]-'a'];
for(int i=1,k=1;i<=n;){
po[i]=now;
auto chk=[&](){
return ok[lp]||ok[rp]||g[lp]>=k-1||g[rp]>=k-1;
};
function<void(int)>upd=[&](int x){
if(x==0||ok[x])return ;
ok[x]=1;upd(a[x].fa);
};
auto go=[&](int o){
int x=po[o];
cmax(g[x],f[o]);
upd(a[x].fa);
};
while(k>1 && !chk()){
--k;
if(a[a[now].fa].len==k)now=a[now].fa;
if(a[a[lp].fa].len==k-1)lp=a[lp].fa;
if(a[a[rp].fa].len==k-1)rp=a[rp].fa;
go(i-k);
}
f[i]=k;
++i;++k;
if(i>n)break;
now=a[now].ch[s[i]-'a'];
rp=a[rp].ch[s[i]-'a'];
lp=a[lp].ch[s[i-1]-'a'];
}
int ans=0;
for(int i=1;i<=n;i++)cmax(ans,f[i]);
cout << ans << '\n';
#ifdef do_while_true
// cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
#endif
return 0;
}