字符串匹配算法

字符串匹配问题的形式定义：

• 文本（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 是有效位移。

解决字符串匹配的算法包括：朴素算法（Naive Algorithm）、Rabin-Karp 算法、有限自动机算法（Finite Automation）、 Knuth-Morris-Pratt 算法（即 、Simon 算法、Colussi 算法、Galil-Giancarlo 算法、Apostolico-Crochemore 算法、Horspool 算法和 Sunday 算法等。

• 朴素的字符串匹配算法（Naive String Matching Algorithm）
• Knuth-Morris-Pratt 字符串匹配算法（即 KMP 算法）
• Boyer-Moore 字符串匹配算法

字符串匹配算法通常分为两个步骤：预处理（Preprocessing）和匹配（Matching）。所以算法的总运行时间为预处理和匹配的时间的总和。

上图描述了常见字符串匹配算法的预处理和匹配时间。

算法导论

Knuth-Morris-Pratt algorithm

Knuth-Morris-Pratt string matching algorithm via Java

Searching for Patterns | Set 2 (KMP Algorithm)

The Knuth-Morris-Pratt Algorithm in my own words

字符串匹配的KMP算法

从头到尾彻底理解KMP

Knuth–Morris–Pratt algorithm

Boyer–Moore string search algorithm

Rabin–Karp string search algorithm

Aho–Corasick string matching algorithm

本文《字符串匹配算法》由 Dennis Gao 发表自博客园博客，任何未经作者本人允许的人为或爬虫转载均为耍流氓。