回文自动机
(Palindromic Automaton) 模板详解
1. 简介
回文自动机（PAM，也称回文树）是一种用于处理字符串中回文子串的高效数据结构。它可以在线性时间内维护字符串中的所有回文子串信息。
主要特点：
线性时间复杂度
在线处理字符串
维护所有回文子串
支持动态添加字符
2. 实现原理
2.1 基本概念
节点结构：
表示一个回文子串
包含长度、后缀链接等信息
后缀链接：
指向最长的回文后缀
用于快速转移状态
2.2 核心策略
状态转移：
利用后缀链接找到匹配位置
维护回文子串的计数
节点维护：
两个初始节点（空串和长度为-1的辅助节点）
动态添加新的回文节点
3. 模板代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869struct PAM { static constexpr int ALPHABET_SIZE = 26; ...
Manacher 算法模板详解
1. 简介
Manacher
算法是一个用于在线性时间内求解字符串中所有位置的最长回文子串长度的算法。它通过巧妙地利用已计算的信息，避免了重复计算。
主要特点：
线性时间复杂度 O(n)
可以处理奇数和偶数长度的回文串
能找到所有位置的最长回文子串
实现简单，易于理解
2. 实现原理
2.1 基本概念
回文串：
正着读和倒着读都一样的字符串
可以是奇数或偶数长度
半径数组：
记录每个位置的回文半径
通过半径可以得到回文长度
2.2 核心策略
字符串预处理：
在字符间插入特殊字符（通常是#）
统一处理奇偶长度的回文串
中心扩展：
利用已知回文串的对称性
尽可能减少重复计算
3. 模板代码
123456789101112131415161718192021std::vector<int> manacher(std::string s) { std::string t = "#"; for (auto c : s) { t += c; t += '#'; } int n ...
后缀数组 (Suffix Array)
模板详解
1. 简介
后缀数组是一种重要的字符串数据结构，它将字符串的所有后缀按字典序排序后得到的数组。配合最长公共前缀（LCP）数组，可以解决许多字符串问题。
主要特点：
O(nlogn) 的构建时间
可以处理字符串的所有后缀
支持高效的字符串匹配
可以解决最长公共子串等问题
2. 实现原理
2.1 基本概念
后缀数组 (SA)：
存储后缀开始位置的有序数组
按后缀字典序排序
名次数组 (Rank)：
每个后缀的排名
SA 数组的逆映射
LCP数组：
相邻后缀的最长公共前缀
用于优化字符串匹配
2.2 核心策略
倍增算法：
逐步增加排序长度
利用已有排序信息
基数排序：
保证稳定性
提高排序效率
3. 模板代码
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061struct SuffixArray { int n; std::v ...
后缀自动机 (Suffix
Automaton) 模板详解
1. 简介
后缀自动机（SAM）是一个强大的字符串处理工具，它可以在线性时间内处理字符串的所有子串信息。这是目前已知的最强大的字符串数据结构之一。
主要特点：
线性时间和空间复杂度
可以处理所有子串信息
支持在线构建
可以解决多种字符串问题
2. 实现原理
2.1 基本概念
状态：
每个状态代表一个子串集合
具有相同 right 集合的子串归为一类
后缀链接：
连接到最长的后缀状态
形成一个树形结构
2.2 核心策略
状态转移：
通过 next 数组记录转移
保持自动机的最小性
状态分裂：
在需要时创建新状态
维护后缀链接的正确性
3. 模板代码
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071struct SAM { static constexpr int ALPHABET_ ...
