题目简析

给定字符串 $S$，要求构造一个字符串序列 $(T_0, T_1, \dots, T_l)$，满足：

1. $T_0$ 是 $S$ 的子串
2. $\forall 1 \le i \le l$，$|T_i| = |T_{i-1}| + 1$（长度递增 $1$）
3. $\forall 1 \le i \le l$，存在 $S$ 的长度为 $|T_i|+1$ 的子串 $S'_i$，使得 $S'_i$ 的前缀为 $T_{i-1}$，后缀为 $T_i$

求最大的 $l$。

算法标签

• 字符串
• 后缀自动机
• 动态规划
• 图论建模
• 最长路径问题

核心条件分析

条件 $3$ 是本题的关键。考虑 $|T_i| = |T_{i-1}| + 1$，那么：

• $T_{i-1}$ 必须是 $T_i$ 的前缀（因为长度差 $1$）
• 存在一个比 $T_i$ 长 $1$ 的串 $S'_i$，以 $T_{i-1}$ 开头，以 $T_i$ 结尾

这意味着 $T_i$ 比 $T_{i-1}$ 多一个字符 $c$，即 $T_i = T_{i-1} + c$，并且 $T_{i-1} + c$ 必须出现在 $S$ 的某个长度为 $|T_i|+1$ 的子串的末尾位置。

问题转化

我们可以将问题建模为在 $S$ 的所有子串上寻找最长链：

• 节点：$S$ 的所有子串（包括空串）
• 边：从 $u$ 到 $v$ 有边当且仅当：
  1. $v = u + c$（$c$ 为某字符）
  2. 存在 $S$ 中一个长度为 $|v|+1$ 的子串，以 $u$ 为前缀，以 $v$ 为后缀

那么问题转化为从空串 $\epsilon$ 出发的最长路径长度。

高效解法

直接枚举所有子串不可行。我们需要利用字符串高级数据结构。

关键观察：条件等价于在 $S$ 中，$u$ 和 $v$ 必须出现在某个长度为 $|v|+1$ 的窗口中，且 $u$ 是前缀，$v$ 是后缀。这提示我们可以用后缀自动机（Suffix Automaton）来刻画所有子串的出现关系。

在后缀自动机中：

• 每个状态对应一组 endpos 集合相同的子串
• 状态之间的转移对应在子串末尾添加字符
• 从初始状态到某个状态的路径对应一个子串

我们定义 $dp[u]$ 为从状态 $u$ 出发的最长链长度。转移为：

其中 $u \xrightarrow{c} v$ 表示存在字符 $c$ 使得从状态 $u$ 经 $c$ 转移到状态 $v$。

最终答案为 $\max dp[u]$。

算法流程

1. 构建 $S$ 的后缀自动机
2. 按状态 $len$ 从大到小排序（拓扑序）
3. 动态规划计算 $dp[u]$
4. 输出最大值

时间复杂度

• 预处理：$O(|S|)$ 构建后缀自动机
• 动态规划：$O(|S|)$ 状态转移
• 总复杂度：$O(|S|)$，适用于 $|S| \le 5 \times 10^5$ 的数据范围

样例验证

以 $S = \text{"abab"}$ 为例：

• 空串 $\to$ $\texttt{"b"}$（通过 $\texttt{"ab"}$）
• $\texttt{"b"}$ $\to$ $\texttt{"ab"}$（通过 $\texttt{"bab"}$）
• $\texttt{"ab"}$ $\to$ $\texttt{"bab"}$（通过 $\texttt{"abab"}$）

链长为 $3$，与样例输出一致。

总结

本题通过将子串关系转化为后缀自动机中的状态转移，利用动态规划在线性时间内求解。核心在于理解条件 $3$ 的本质是要求相邻子串在某个公共窗口中以特定位置关系出现，这恰好对应自动机中的字符转移关系。