tag：Suffix Tree，Dp
定义字符串数组 \(t_{1\dots k}\) 合法当且仅当 \(t_{i}\) 是 \(t_{i-1}\) 的字串且 \(t_i\ne t_{i-1}\)
给定字符串 \(s\)，求最大的 \(k\) 使得可以将 \(s\) 提取出 \(k\) 个不相交的区间，依次排序后得到的字符串数组合法。
\(|s|\le 5\times 10^5\)
最优决策下我们必然让长度单调递减，每次恰好减 \(1\)。
枚举区间 \([i,j]\)，然后连边，我们可以做到 \(\mathcal O(n^3)\) 的连边，然后就是一个 DAG 最长路的问题了。
进一步观察，我们每个串可以用后缀树上一个节点 \(\rm +~end\) 的位置表示。
注意到长度上界至多为 \(1+2+...+cnt=|s|\)，即 \(cnt=\sqrt{|s|}\)，于是我们可以得到一个 \(\mathcal O(|s|\sqrt{|s|})\) 的做法。
实际上最优决策是固定的，每种字符都会被固定在一个合法的最右点。
好像非常有道理：
设 \(f_i\) 表示以 \(i\) 为结尾最长合法的字符串数组。
直觉上从后往前让 \(f_i\) 增加就好了。
于是转移为 \(f_i=\max(f_{j})+1,j\ge i+f_i,s_{j-f_j+1...j}\subseteq s_{i-f_i+1...i}\)
接下来可以证明 \(f_{i}\ge f_{i+1}-1\)
将 \(i+1\) 的结尾删去之后显然 \(f_i\) 是合法的。
于是不难得到做法，从后往前 Dp，每个 \(f_i\) 从 \(f_{i+1}-1\) 开始枚举长度 \(L\)，那么只需要 check，对于长度 \(L\)，我们只需要检查是否存在字符 \([i+L,n]\)
然后可以考虑在移动的时候暴力维护 \(r\) 的移动...大概就没了吧？
然而仔细做了一下，这样貌似非常不好做...
于是只能改成 Dp 状态，设为 \(f_i\) 表示以 \(i\) 为开头的最长的答案。
不难得到 \(f_{i+1}\ge f_i-1\)，于是得到 \(f_i\le f_{i+1}+1\)
于是需要 check 的区间就是 \(i+f_i\) 这段区间，不难注意到这个值是不增的，所以直接扫就可以了！
原文：https://www.cnblogs.com/Soulist/p/13709248.html