最长重复子串（后缀自动机解法）

题目描述：
给定一个字符串s，要求找出其中最长的重复子串。重复子串是指在字符串中至少出现两次的连续子串（出现位置可以重叠，但通常我们考虑不重叠的情况）。使用后缀自动机（Suffix Automaton, SAM）这一高效数据结构来解决。

解题过程：

1. 理解后缀自动机的基本概念

   • 后缀自动机是一个能接受字符串所有后缀的最小确定性有限状态自动机
   • 每个状态代表一组endpos（结束位置）相同的子串
   • 关键属性：len[i]表示状态i能接受的最长子串长度

2. 构建后缀自动机

   • 初始化：只有一个初始状态，len=0，link=-1
   • 逐个添加字符，维护last指针指向当前状态
   • 对于新字符c：
     a. 创建新状态cur，len[cur] = len[last] + 1
     b. 从last开始沿link指针回溯，为没有c转移的状态添加指向cur的转移
     c. 如果回溯到初始状态仍未找到c转移，设置link[cur]=0
     d. 否则，找到第一个有c转移的状态p，设q=trans[p][c]

3. 处理特殊情况（重点）

   • 如果len[q] == len[p] + 1，直接设置link[cur] = q
   • 否则需要克隆状态：
     • 创建新状态clone，复制q的转移和link
     • len[clone] = len[p] + 1
     • 将q和cur的link指向clone
     • 从p开始回溯，将指向q的c转移重定向到clone

4. 计算重复子串信息

   • 在构建过程中维护每个状态的出现次数（size）
   • 通过link指针形成的树进行拓扑排序（按len降序）
   • 从叶子节点向上传递size值

5. 寻找最长重复子串

   • 遍历所有状态，找到满足size>1且len最大的状态
   • 该状态的len值就是最长重复子串的长度
   • 可以通过在自动机上回溯找到具体子串

6. 时间复杂度分析

   • 构建后缀自动机：O(n)
   • 计算出现次数：O(n)
   • 总体复杂度：线性O(n)，优于动态规划的O(n²)

关键理解点：

• 后缀自动机通过状态复用高效表示所有子串
• link指针形成了后缀链接树，体现了子串的包含关系
• 每个状态的len属性直接给出了该状态代表的最长子串长度
• 通过size>1可以快速识别重复出现的子串

这种解法将看似需要O(n²)的问题通过精巧的数据结构优化到线性时间复杂度，展示了算法设计的精妙之处。