字符串

字符串是由字符连接而成的序列，是计算机科学中最基础的数据类型之一。字符串算法在文本处理、搜索引擎、生物信息学等领域有广泛应用。

常见问题类型

• 字符串匹配：在文本中查找模式串出现的位置
• 子串问题：处理字符串的连续片段
• 前缀/后缀问题：处理字符串的开头和结尾部分
• 回文串问题：处理正读反读相同的字符串
• 子序列问题：处理不连续但保持相对顺序的字符序列

章节目录

基础知识

字符串匹配

自动机与多模式匹配

后缀结构

回文串

其他

算法选择指南

flowchart TD
    A[字符串问题] --> B{单模式 or 多模式?}
    
    B -->|单模式匹配| C{需要什么?}
    B -->|多模式匹配| D[AC自动机]
    
    C -->|简单实现| E[字符串哈希]
    C -->|稳定高效| F[KMP]
    C -->|实践最快| G[Boyer-Moore]
    
    A --> H{后缀相关?}
    H -->|是| I{在线/离线?}
    I -->|离线| J[后缀数组]
    I -->|在线/复杂查询| K[后缀自动机]
    
    A --> L{回文相关?}
    L -->|所有回文| M[Manacher]
    L -->|本质不同| N[回文树]