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

我将为你讲解如何使用后缀自动机解决最长重复子串问题。这是一个比后缀数组更简洁高效的解决方案。

问题描述

给定一个字符串s，找到最长的子串，使得这个子串在s中至少出现两次。重复出现的子串可以重叠。

示例：

• 输入："banana"
• 输出："ana"（在位置1-3和3-5各出现一次）

解题思路

核心概念：后缀自动机

后缀自动机是一个能接受字符串所有后缀的最小有限状态自动机。它包含了字符串所有子串的信息，是解决字符串问题的强大工具。

关键性质

1. 每个状态代表一组结束位置集合相同的子串
2. 状态间的转移构成一个有向无环图
3. 从初始状态到任意状态的路径对应一个子串

详细解题步骤

步骤1：理解后缀自动机的基本结构

后缀自动机中的每个状态包含：

• len：该状态能接受的最长子串长度
• link：后缀链接，指向接受较短后缀的状态
• next：字符转移函数

class State:
    def __init__(self, length):
        self.len = length      # 该状态对应的最长子串长度
        self.link = None       # 后缀链接
        self.next = {}         # 转移函数

步骤2：构建后缀自动机

我们使用在线算法逐个添加字符：

class SuffixAutomaton:
    def __init__(self):
        # 初始状态，长度为0，后缀链接为None
        self.last = self.root = State(0)
        self.states = [self.root]
    
    def extend(self, c):
        # 创建新状态，长度为last.len + 1
        cur = State(self.last.len + 1)
        self.states.append(cur)
        
        # 从last开始，沿着后缀链接设置转移
        p = self.last
        while p is not None and c not in p.next:
            p.next[c] = cur
            p = p.link
        
        if p is None:
            # 情况1：c是全新字符
            cur.link = self.root
        else:
            q = p.next[c]
            if p.len + 1 == q.len:
                # 情况2：q正好是p的后继
                cur.link = q
            else:
                # 情况3：需要分裂状态
                clone = State(p.len + 1)
                clone.next = q.next.copy()
                clone.link = q.link
                
                # 更新q和cur的后缀链接
                q.link = clone
                cur.link = clone
                
                # 更新p及其后缀链接路径上的转移
                while p is not None and p.next.get(c) == q:
                    p.next[c] = clone
                    p = p.link
                
                self.states.append(clone)
        
        self.last = cur

步骤3：计算每个状态的结束位置数量

为了找到重复出现的子串，我们需要知道每个状态对应的子串在字符串中出现的次数：

def calculate_occurrences(sam, s):
    # 初始化出现次数
    for state in sam.states:
        state.cnt = 0
    
    # 遍历所有状态，非初始状态的叶子节点出现次数为1
    p = sam.last
    while p is not None:
        p.cnt += 1
        p = p.link
    
    return sam

步骤4：寻找最长重复子串

遍历所有状态，找到出现次数≥2且长度最长的状态：

def longest_repeating_substring(s):
    # 构建后缀自动机
    sam = SuffixAutomaton()
    for char in s:
        sam.extend(char)
    
    # 计算出现次数
    sam = calculate_occurrences(sam, s)
    
    # 寻找最长重复子串
    max_len = 0
    best_state = None
    
    for state in sam.states:
        if state.cnt >= 2 and state.len > max_len:
            max_len = state.len
            best_state = state
    
    if best_state is None:
        return ""
    
    # 重建最长重复子串
    # 从best_state沿着后缀链接回溯到根节点
    result = []
    current = best_state
    
    # 我们需要找到到达这个状态的具体路径
    # 在实际实现中，我们通常记录每个状态的第一个出现位置
    return find_substring_by_state(s, best_state)

def find_substring_by_state(s, state):
    # 简化方法：遍历所有子串，找到长度等于state.len的
    # 在实际高效实现中，我们会在构建时记录信息
    n = len(s)
    target_len = state.len
    
    for i in range(n - target_len + 1):
        substring = s[i:i + target_len]
        count = 0
        for j in range(n - target_len + 1):
            if s[j:j + target_len] == substring:
                count += 1
            if count >= 2:
                return substring
    
    return ""

步骤5：完整优化实现

实际应用中，我们会在构建过程中记录更多信息：

class OptimizedSuffixAutomaton:
    def __init__(self, s):
        self.states = [State(0)]
        self.last = 0
        self.s = s
        
        # 构建自动机
        for i, c in enumerate(s):
            self.extend(c, i + 1)
        
        # 计算每个状态的出现次数
        self.calculate_occurrences()
    
    def extend(self, c, pos):
        # 创建新状态
        cur = len(self.states)
        self.states.append(State(self.states[self.last].len + 1))
        self.states[cur].first_pos = pos - 1  # 记录第一次出现位置
        
        p = self.last
        while p != -1 and c not in self.states[p].next:
            self.states[p].next[c] = cur
            p = self.states[p].link
        
        if p == -1:
            self.states[cur].link = 0
        else:
            q = self.states[p].next[c]
            if self.states[p].len + 1 == self.states[q].len:
                self.states[cur].link = q
            else:
                # 分裂状态
                clone = len(self.states)
                self.states.append(State(self.states[p].len + 1))
                self.states[clone].next = self.states[q].next.copy()
                self.states[clone].link = self.states[q].link
                self.states[clone].first_pos = self.states[q].first_pos
                
                self.states[q].link = clone
                self.states[cur].link = clone
                
                while p != -1 and self.states[p].next.get(c) == q:
                    self.states[p].next[c] = clone
                    p = self.states[p].link
        
        self.last = cur
    
    def calculate_occurrences(self):
        # 拓扑排序（按len降序）
        states_sorted = sorted(range(len(self.states)), 
                              key=lambda i: self.states[i].len, reverse=True)
        
        # 初始化计数
        for i in range(len(self.states)):
            self.states[i].cnt = 0
        
        # 叶子节点计数为1
        p = self.last
        while p != -1:
            self.states[p].cnt += 1
            p = self.states[p].link
        
        # 沿后缀链接传递计数
        for i in states_sorted:
            if self.states[i].link != -1:
                self.states[self.states[i].link].cnt += self.states[i].cnt
    
    def find_longest_repeating(self):
        max_len = 0
        best_state = -1
        
        for i, state in enumerate(self.states):
            if state.cnt >= 2 and state.len > max_len:
                max_len = state.len
                best_state = i
        
        if best_state == -1:
            return ""
        
        # 从第一次出现位置和长度重建子串
        pos = self.states[best_state].first_pos
        length = self.states[best_state].len
        start_pos = pos - length + 1
        
        return self.s[start_pos:start_pos + length]

算法分析

时间复杂度：O(n)，其中n是字符串长度
空间复杂度：O(n)

示例演示

以字符串"banana"为例：

1. 构建后缀自动机，得到多个状态
2. 计算每个状态的出现次数：
   • 状态对应"ana"：出现2次
   • 状态对应"na"：出现2次
   • 状态对应"a"：出现3次
3. 最长且出现≥2次的是"ana"，长度为3

关键理解点

1. 后缀链接：连接接受相同后缀不同长度的状态
2. 状态分裂：当新字符导致状态需要拆分时的处理
3. 出现次数计算：通过后缀链接反向传播计数

这种方法相比暴力解法的O(n³)和后缀数组的O(n log n)更加高效，是解决最长重复子串问题的最佳方案之一。