常见字符串匹配算法
更新时间
浏览
TIP
本文主要是介绍 常见字符串匹配算法 。
# 字符串匹配算法]
# 字符串匹配问题的形式定义：
- **文本（Text）**是一个长度为 n 的数组 T[1..n]；
- **模式（Pattern）**是一个长度为 m 且 m≤n 的数组 P[1..m]；
- T 和 P 中的元素都属于有限的字母表 Σ 表；
- 如果 0≤s≤n-m，并且 T[s+1..s+m] = P[1..m]，即对 1≤j≤m，有 T[s+j] = P[j]，则说模式 P 在文本 T 中出现且位移为 s，且称 s 是一个有效位移（Valid Shift）。
比如上图中，目标是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出现。该模式在此文本中仅出现一次，即在位移 s = 3 处，位移 s = 3 是有效位移。
# 解决字符串匹配的常用算法包括：
- BF算法(Brute Force)
- MP算法(Morris-Pratt)
- KMP算法(Knuth-Morris-Pratt)
- BM算法(Boyer-Moore)
- BMH算法
- Needleman–Wunsch算法
- Trie 树(字典树)算法
- AC自动机算法
- RK(Rabin-Karp)算法
# 字符串匹配算法通常分为两个步骤：
预处理(Preprocessing)和匹配(Matching)。所以算法的总运行时间为预处理和匹配的时间的总和。
# 参考文章
- https://www.cnblogs.com/gaochundong/p/string_matching.html
- https://www.cnblogs.com/magic-sea/tag/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95/
