分析
为了方便，把串翻转，条件改为「使 $t_{i-1}$ 是 $t_i$ 的真子串」。
可以发现一个性质，即在一定存在一组最优解使得 $|t_i|=i$，因为某个不满足的串删去多的部分一定不会差。
于是可以考虑一个 DP。设 $dp_i$ 表示最后一个串以 $i$ 结尾时最多能选出多少个串。
然而这个似乎没法转移。冷静分析一下可以发现一定有 $dp_{i-1}\geq dp_i-1$（考虑一个最后一个串以 $i$ 结尾且包含 $dp_i$ 个串的方案，将方案中所有串删去最后一个字符后显然仍然合法，且此时构成一组最后一个串以 $i-1$ 结尾且包含 $dp_i-1$ 个串的方案）。于是我们可以从 $dp_{i-1}+1$ 往下枚举 $dp_i$ 并判断是否合法。可以发现总 check 次数是 $\mathcal{O}(n)$ 的。
考虑如何 check $dp_i=x$ 是否合法。我们相当于要判断 $s_{1..i-x}$ 的所有子串中是否有一个长度为 $x-1$ 的、满足是 $s_{i-x+1,i}$ 的子串且其结尾的 $dp$ 值 $\geq x-1$。
前面那个条件不好处理，可以转化为存在一个 $p\leq i-x$，满足前缀 $p$ 与前缀 $i$ 或前缀 $i-1$ 的最长公共后缀长度 $\geq x-1$。
注意到在整个过程中 $i-x$ 是不降的，因此我们可以用一个指针维护可能的范围；最长公共后缀的条件可以建出 SAM，在 Parent 树上找到前缀 $i$ 和前缀 $i-1$ 对应的点向上倍增找到最小的 $len_u\geq x-1$，则子树 $u$ 中所有点都满足该条件；$dp$ 值的条件可以直接查询子树中范围内的最大的 $dp$ 值并判断，DFS 序+线段树即可。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=1000000+10;
int n,dp[N]; char s[N];
int last,cnt;
int fa[N],ch[N][26],len[N],pos[N];
void extend(int c) {
int p=last,np=++cnt; last=np,len[np]=len[p]+1;
for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if (!p) fa[np]=1;
else {
int q=ch[p][c];
if (len[p]+1==len[q]) fa[np]=q;
else {
int nq=++cnt; len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q],fa[q]=fa[np]=nq;
for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
}
vector<int> E[N];
int f[20][N],dfn[N],low[N],tim=0;
void dfs(int u) {
dfn[u]=++tim; f[0][u]=fa[u];
for (int i=1;i<=19;++i) f[i][u]=f[i-1][f[i-1][u]];
for (int v:E[u]) dfs(v);
low[u]=tim;
}
int jump(int u,int lim) {
for (int i=19;~i;--i)
if (len[f[i][u]]>=lim) u=f[i][u];
return u;
}
#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2];
void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
void modify(int o,int l,int r,int p,int w) {
if (l==r) { maxv[o]=w; return; }
int mid=(l+r)>>1;
if (p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
if (!ql||!qr) return 0;
if (ql<=l&&r<=qr) return maxv[o];
int mid=(l+r)>>1,res=0;
if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
return res;
}
int check(int i) {
int a=jump(pos[i],dp[i]-1),b=jump(pos[i-1],dp[i]-1);
return query(1,1,cnt,dfn[a],low[a])>=dp[i]-1||
query(1,1,cnt,dfn[b],low[b])>=dp[i]-1;
}
int main() {
n=read(); scanf("%s",s+1); reverse(s+1,s+n+1);
last=cnt=1;
for (int i=1;i<=n;++i) extend(s[i]-'a'),pos[i]=last;
for (int i=2;i<=cnt;++i) E[fa[i]].emplace_back(i);
dfs(1);
for (int i=1,p=0;i<=n;++i) {
dp[i]=dp[i-1]+1;
while (!check(i)) --dp[i],++p,modify(1,1,cnt,dfn[pos[p]],dp[p]);
}
int ans=0;
for (int i=1;i<=n;++i) ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}