字符串

字符串匹配

字符串匹配是在文本串中查找模式串出现位置的过程。

特点

1. 预处理时间： 或 ，其中 是模式串长度， 是字符集大小
2. 匹配时间：从 到 不等
3. 适用于文本搜索、生物序列比对等场景

分类

朴素匹配			简单直观
KMP			线性时间
Sunday			实际效率高
Boyer-Moore			从右向左匹配
AC自动机			多模式匹配

字符串哈希

字符串哈希是将字符串映射为整数的技术。

特点

1. 预处理时间：
2. 查询时间：
3. 适用于快速字符串比较和子串查询

分类

字典树

字典树（Trie）是一种用于高效存储和查找字符串的树形数据结构。

特点

1. 插入/查找时间：，其中 是字符串长度
2. 空间复杂度：
3. 适用于前缀统计、字符串集合维护等场景

分类

回文串

回文串是正反读都相同的字符串。

特点

1. 判断时间：
2. 预处理时间：（Manacher算法）
3. 适用于回文串查找、统计等场景

分类

中心扩展	查找最长回文子串
Manacher	查找最长回文子串
动态规划	统计回文子串个数

应用场景对比

字符串匹配适合：

1. 文本搜索和替换
2. 生物序列比对
3. 网络入侵检测

字符串哈希适合：

1. 快速字符串比较
2. 子串查询
3. 字符串去重

字典树适合：

1. 前缀统计
2. 自动补全
3. 字符串集合维护

回文串算法适合：

1. 最长回文子串查找
2. 回文子序列统计
3. 文本特征分析

选择建议

1. 单模式匹配选择KMP
2. 多模式匹配选择AC自动机
3. 需要快速比较子串选择字符串哈希
4. 维护字符串集合选择字典树
5. 处理回文串选择Manacher算法