原题面很简洁，懒得概括了。

思路

后缀自动机 + 结论。

这种题出题人没有十年脑血栓都没法出。

结论 1：\(s_{i - 1}\) 必定是 \(s_i\) 的后缀。

考虑 \(s_i\) 中 \(s_{i - 1}\) 最后一次出现位置，记为 \(p\)。对于 \(s_i\) 中 \(p\) 之后的位置，把它们截去不影响 \(s_{i - 1}\) 在 \(s_i\) 中的出现次数，并且 \(s_i\) 在 \(s_{i + 1}\) 中的出现次数可能增加，因此截去一定不劣，故而可以令 \(s_{i - 1}\) 必定为 \(s_i\) 的后缀。

结合 parent tree 的性质：祖先结点必定是后代结点的后缀，可以联想到在 parent tree 上跑一次从上到下的 dp 求最长链，dp 转移的条件是祖先结点代表的串在后代的串中至少出现 \(2\) 次。

如何判定转移的条件？

考虑到祖先串一定是后代串的后缀，即至少在后代串中出现 \(1\) 次。令 \(u, v\) 分别为祖先串和后代串，\(p\) 为 \(\operatorname{endpos}(v)\) 中任意元素，则当 \(\operatorname{endpos}(u)\) 中包含 \([p - len(v) + len(u), p - 1]\) 中任意元素时，\(u\) 在 \(v\) 中至少出现 \(2\) 次。

于是可以考虑用线段树合并维护每个结点的 \(\operatorname{endpos}\)，判定可以 \(O(\log)\) 用线段树查询。

然而现在的问题是：parent tree 上的结点代表整个等价类，转移的时候应该用哪一个串？

结论 2：转移时等价类中所有串都是等价的。

考虑反证。假设 \(s\) 是某一结点 \(u\) 表示的等价类中最长的串，\(v\) 是结点 \(u\) 的祖先，串 1 和串 2 都是结点 \(v\) 的等价类中的串。

不妨假定串 1 是 \(\rm abcb\)，串 2 是 \(\rm babcb\)，串 \(s\) 是 \(\rm abcbabcb\)，则串 \(1, s\) 之间可以转移而串 \(2, s\) 之间不可以转移。

如果存在另一个可以和串 2 转移的串 3，不妨假定为 \(\rm babcbabcb\)，那么因为 \(s\) 是 \(u\) 等价类中最长的串，所以串 3 一定来自另一个以 \(v\) 为祖先的等价类中。

在上面的反例中，串 3 所在的等价类以 \(u\) 为祖先，记这个等价类为 \(w\)。根据 parent tree 的定义有：

\(|\operatorname{endpos}(u)| > |\operatorname{endpos}(w)|\)

也就是存在位置 \(p \in |\operatorname{endpos}(u)| - |\operatorname{endpos}(w)|\) 使得该位置存在串 \(s\) 而不存在串 3.

那么该位置出现了 \(2\) 次串 1 而只出现了 \(1\) 次串 \(2\)，与串 1 和串 2 在同一等价类中矛盾，得证。

所以转移的时候只需要取最长串即可。

那么在 parent tree 上进行一次从上往下的 dp 求最长链，转移的时候用线段树判定即可。

代码

有亿 丶难调。

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 2e5 + 5;
const int sam_sz = maxn << 1;
const int t_sz = 1e7 + 5;

inline int max(const int &a, const int &b) { return (a >= b ? a : b); }

int n;
int rt[sam_sz];
int dp[sam_sz], from[sam_sz];
char s[maxn];

namespace SGT
{
    int cnt;
    int ls[t_sz], rs[t_sz];

    int insert(int l, int r, int p)
    {
        int k = ++cnt;
        if (l == r) return k;
        int mid = (l + r) >> 1;
        if (p <= mid) ls[k] = insert(l, mid, p);
        else rs[k] = insert(mid + 1, r, p);
        return k;
    }

    int merge(int a, int b)
    {
        if ((!a) || (!b)) return a | b;
        int k = ++cnt;
        ls[k] = merge(ls[a], ls[b]);
        rs[k] = merge(rs[a], rs[b]);
        return k;
    }

    bool query(int k, int l, int r, int ql, int qr)
    {
        if (!k) return false;
        if ((l >= ql) && (r <= qr)) return true;
        int mid = (l + r) >> 1;
        if ((ql <= mid) && query(ls[k], l, mid, ql, qr)) return true;
        if ((qr > mid) && query(rs[k], mid + 1, r, ql, qr)) return true;
        return false;
    }
}

namespace SAM
{
    int cur, lst;
    int seq[sam_sz], pos[sam_sz], cnt[sam_sz];
    int len[sam_sz], fa[sam_sz], son[sam_sz][26];

    void copy_node(int to, int from)
    {
        len[to] = len[from], fa[to] = fa[from], pos[to] = pos[from];
        memcpy(son[to], son[from], sizeof(son[to]));
    }

    void insert(int c, int cp)
    {
        int p = lst, np = lst = ++cur;
        len[np] = len[p] + 1, pos[np] = cp;
        for ( ; ~p && (!son[p][c]); p = fa[p]) son[p][c] = np;
        if (!~p) fa[np] = 0;
        else
        {
            int q = son[p][c];
            if (len[q] == len[p] + 1) fa[np] = q;
            else
            {
                int nq = ++cur;
                copy_node(nq, q);
                len[nq] = len[p] + 1;
                fa[q] = fa[np] = nq;
                for ( ; ~p && (son[p][c] == q); p = fa[p]) son[p][c] = nq;
            }
        }
    }

    void sort()
    {
        for (int i = 1; i <= cur; i++) cnt[len[i]]++;
        for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
        for (int i = 1; i <= cur; i++) seq[cnt[len[i]]--] = i;
    }

    void solve()
    {
        for (int i = 1, t = 0; i <= n; i++)
        {
            t = son[t][s[i] - 'a'];
            rt[t] = SGT::insert(1, n, i);
        }
        // printf("debug %d\n", seq[1]);
        for (int i = cur; i; i--) rt[fa[seq[i]]] = SGT::merge(rt[fa[seq[i]]], rt[seq[i]]);
        int ans = 1;
        for (int i = 1; i <= cur; i++)
        {
            int x = seq[i];
            if (!fa[x]) dp[x] = 1, from[x] = x;
            else
            {
                // puts("nmsl");
                int anc = from[fa[x]];
                // printf("[%d, %d]\n", anc, x);
                if (SGT::query(rt[anc], 1, n, pos[x] - len[x] + len[anc], pos[x] - 1)) dp[x] = dp[fa[x]] + 1, from[x] = x;
                else dp[x] = dp[fa[x]], from[x] = from[fa[x]];
            }
            ans = max(ans, dp[x]);
        }
        printf("%d\n", ans);
    }
}

int main()
{
    scanf("%d%s", &n, s + 1);
    SAM::fa[0] = -1;
    for (int i = 1; i <= n; i++) SAM::insert(s[i] - 'a', i);
    SAM::sort();
    SAM::solve();
    return 0;
}