在字符串处理领域，Rust回文树（也称为回文自动机）是一种高效的数据结构，用于快速统计和查询字符串中所有不同的回文子串。本教程将手把手教你如何用Rust语言实现一个完整的回文树，即使你是Rust初学者也能轻松上手。
什么是回文树？
回文树（Palindromic Tree），又称Eertree，是由Mikhail Rubinchik在2015年提出的一种数据结构。它能够在线性时间内构建，并支持动态添加字符、统计不同回文子串数量、查询最长回文后缀等操作。
回文树的核心思想
回文树包含两类节点：
- 奇根节点：代表长度为-1的虚拟回文串（用于处理奇数长度回文）
- 偶根节点：代表长度为0的空回文串（用于处理偶数长度回文）
每个节点存储以下信息：
- 回文串的长度
- 指向其最长回文后缀的fail指针
- 子节点映射（通过字符跳转）
- 出现次数（可选）
Rust实现步骤
下面我们用字符串处理Rust的方式逐步实现回文树。
1. 定义节点结构
#[derive(Default)]struct Node { len: i32, // 回文串长度 fail: usize, // fail指针 next: [usize; 26], // 子节点（假设只处理小写字母） count: usize, // 出现次数}impl Node { fn new(len: i32) -> Self { Node { len, fail: 0, next: [0; 26], count: 0, } }}
2. 定义回文树结构
struct PalindromicTree { nodes: Vec<Node>, last: usize, // 当前最长回文后缀对应的节点 s: Vec<u8>, // 输入字符串的字符数组 n: usize, // 当前处理到的位置}impl PalindromicTree { fn new() -> Self { let mut nodes = Vec::new(); // 节点0：偶根（长度0） nodes.push(Node::new(0)); // 节点1：奇根（长度-1） nodes.push(Node::new(-1)); // 奇根的fail指向自己 nodes[1].fail = 1; // 偶根的fail指向奇根 nodes[0].fail = 1; PalindromicTree { nodes, last: 0, s: vec![0], // 添加哨兵 n: 0, } }}
3. 实现扩展函数
关键在于找到当前位置能形成的新回文串：
impl PalindromicTree { fn extend(&mut self, c: u8) { self.s.push(c); self.n += 1; let ci = (c - b'a') as usize; let mut cur = self.last; // 找到满足 s[n - len[cur] - 1] == s[n] 的cur while self.s[self.n - self.nodes[cur].len as usize - 1] != c { cur = self.nodes[cur].fail; } if self.nodes[cur].next[ci] != 0 { // 已存在该回文串 self.last = self.nodes[cur].next[ci]; self.nodes[self.last].count += 1; return; } // 创建新节点 let new_node = self.nodes.len(); self.nodes.push(Node::new(self.nodes[cur].len + 2)); self.nodes[cur].next[ci] = new_node; // 设置fail指针 if self.nodes[new_node].len == 1 { // 长度为1，fail指向偶根 self.nodes[new_node].fail = 0; } else { // 找到最长回文后缀 let mut tmp = self.nodes[cur].fail; while self.s[self.n - self.nodes[tmp].len as usize - 1] != c { tmp = self.nodes[tmp].fail; } self.nodes[new_node].fail = self.nodes[tmp].next[ci]; } self.last = new_node; self.nodes[self.last].count = 1; }}
4. 使用示例
fn main() { let s = "ababa"; let mut tree = PalindromicTree::new(); for c in s.bytes() { tree.extend(c); } // 不同回文子串数量 = 节点数 - 2（减去两个根节点） println!("不同回文子串数量: {}", tree.nodes.len() - 2); // 输出所有回文串长度 for (i, node) in tree.nodes.iter().enumerate() { if i > 1 { // 跳过根节点 println!("回文串长度: {}, 出现次数: {}", node.len, node.count); } }}
为什么选择Rust实现回文自动机？
使用Rust算法实现回文树有诸多优势：
- 内存安全：避免C++中常见的指针错误
- 零成本抽象：性能接近C/C++
- 强大的类型系统：编译期捕获错误
- 所有权模型：自动管理内存，无需垃圾回收
总结
通过本教程，你已经掌握了Rust回文树的基本原理和完整实现。回文自动机是处理回文相关问题的强大工具，在竞赛编程和实际应用中都有广泛用途。建议你动手实践，尝试添加更多功能如输出具体回文串、处理Unicode字符等。
记住，掌握字符串处理Rust技巧不仅能提升算法能力，还能加深对Rust语言特性的理解。继续练习，你将成为Rust算法高手！
来源：
https://www.vpshk.cn/