本书是一本不可多得的字符串匹配方面的专业书籍，主要关注那些在实际应用中性能最好的算法和相应的实现。本书的内容简洁清晰，示例以分步的形式给出，算法以伪代码的形式给出，对于同个问题的多种算法更是通过实验性能效果图的形式给出，这为那些试图尽快为自己的应用找到最合适算法的读者提供了极大的方便。

本书可帮助本领域的研究人员从整体上把握字符串匹配方面的脉络，而其他相关领域的人员也可借助本书非常清晰地了解串匹配问题的概况。

书中对串匹配问题进行了系统化的分类，从实际效果出发，着重详细介绍了串匹配领域内效果最好的若干种算法。并且给出了具有统一接口的算法伪码，使读者能清晰理解算法原理，易于实现算法编程，从而提高专业水平。此外，书中通过严谨的理论分析和大量实验数据，说明了每种算法在实际应用中的适用范围，由此提供了良好的应用指导，解决了串匹配算法的最佳适用性问题。

第1章 导言

1.1 本书的目的和侧重点

1.2 概况

1.3 基本概念

1.3.1 位并行和位运算

1.3.2 带标记的有根树和trie

1.3.3 自动机

1.3.4 复杂度表示法

第2章 字符串匹配

2.1 基本概念

2.2 基于前缀搜索的方法

2.2.1 Knuth-Morris-Pratt算法的思想

2.2.2 Shift-And/Shift-Or算法

2.3 基于后缀搜索的方法

2.3.1 Boyer-Moore算法的思想

2.3.2 Horspool算法

2.4 基于子串搜索的方法

2.4.1 BDM算法的思想

2.4.2 BNDM算法

2.4.3 BOM算法

2.5 实验图

2.6 其他算法和参考文献

第3章 多字符串匹配

3.1 基本概念

3.2 基于前缀搜索的方法

3.2.1 Multiple Shift-And算法

3.2.2 基本的Aho-Corasick算法

3.2.3 高级的Aho-Corasick算法

3.3 基于后缀搜索的方法

3.3.1 Commentz-Walter算法的思想

3.3.2 Set Horspool算法

3.3.3 Wu-Manber算法

3.4 基于子串搜索的方法

3.4.1 Multiple BNDM算法

3.4.2 SBDM算法的思想

3.4.3 SBOM算法

3.5 实验图

3.6 其他算法和文献

第4章 扩展字符串匹配

4.1 基本概念

4.2 字符组

4.2.1 模式串中的字符组

4.2.2 文本中的字符组

4.3 限长空位

4.3.1 Shift-And算法扩展

4.3.2 BNDM算法扩展76

4.4 可选字符

4.5 通配符和重复字符

4.5.1 Shift-And算法扩展

4.5.2 BNDM算法扩展

4.6 多模式串搜索

4.7 其他算法和参考文献

第5章 正则表达式匹配

5.1 基本概念

5.2 构造NFA

5.2.1 Thompson自动机

5.2.2 Glushkov自动机

5.3 搜索正则表达式的经典方法

5.3.1 Thompson的NFA模拟

5.3.2 使用确定自动机

5.3.3 混合方法

5.4 位并行算法

5.4.1 位并行Thompson

5.4.2 位并行Glushkov

5.5 过滤方法

5.5.1 多字符串匹配方法

5.5.2 Gnu的基于必要因子的启发式方法

5.5.3 基于BNDM的方法

5.6 实验结果

5.7 其他算法与参考资料

5.8 构造解析树

第6章 近似匹配

6.1 基本概念

6.2 动态规划算法

6.2.1 编辑距离的计算

6.2.2 在文本中搜索

6.2.3 平均情况下的改进

6.2.4 其他基于动态规划的算法

6.3 基于自动机的算法

6.4 位并行算法

6.4.1 并行化NFA

6.4.2 并行化动态规划矩阵

6.5 文本快速过滤算法

6.5.1 k+1分片算法

6.5.2 近似BNDM算法

6.5.3 其他过滤算法

6.6 多模式串近似搜索

6.6.1 仅允许一个错误的散列算法

6.6.2 多模式串的k+1分片算法

6.6.3 重叠自动机算法

6.7 扩展字符串和正则表达式的近似搜索

6.7.1 基于动态规划的方法

6.7.2 Four-Russians方法

6.7.3 位并行方法

6.8 实验图

6.9 其他算法和参考文献

第7章 总结

7.1 软件资源

7.1.1 Gnu Grep

7.1.2 Wu和Manber的Agrep

7.1.3 Navarro的Nrgrep

7.1.4 Mehldau和Myers的Anrep

7.1.5 计算生物学方面的资料

7.2 其他书籍

7.2.1 串匹配方面

7.2.2 计算生物学方面

7.3 其他资源

7.3.1 期刊

7.3.2 会议

7.3.3 在线资源

7.4 相关主题

7.4.1 索引

7.4.2 压缩文本中的搜索

7.4.3 重复和循环

7.4.4 二维和多维的模式匹配

7.4.5 树模式匹配

7.4.6 序列比较

7.4.7 特异子串检测

参考文献

索引