前缀表与KMP算法
KMP(Knuth-Morris-Pratt)算法是一种用于字符串匹配的高效算法,它能够在文本串中查找模式串出现的位置。KMP算法的核心在于避免重复比较字符,从而提高匹配效率。
KMP算法的基本思路
- 预处理模式串:通过构建一个“部分匹配表”(或称为“失配表”),在模式串中记录每个位置的最长可匹配前缀长度。
- 匹配过程:利用部分匹配表,在匹配失败时,根据前缀信息跳过不必要的比较,从而加速匹配过程。
部分匹配表(LPS数组)
LPS(Longest Prefix Suffix)数组用于存储模式串的每个前缀的最长相等前后缀的长度。具体构建方式如下:
- **LPS[i]**:表示模式串的前缀(
pattern[0]
到pattern[i]
)的最长相等前后缀的长度。
KMP算法实现
下面是KMP算法的完整实现,包括LPS数组的构建和匹配过程:
1 |
|
代码解析
- computeLPS函数:构建LPS数组,遍历模式串并填充LPS数组,使用回溯逻辑。
- KMPSearch函数:使用LPS数组进行模式匹配:
- 使用两个指针
i
和j
分别指向文本和模式串。 - 如果字符匹配,两个指针同时移动。
- 如果模式串匹配完成,将起始位置保存。
- 如果不匹配,根据LPS数组调整模式指针。
- 使用两个指针
复杂度分析
- 时间复杂度:O(n + m),其中 n 是文本串的长度,m 是模式串的长度。
- 空间复杂度:O(m),用于存储LPS数组。
KMP算法是一个非常高效的字符串匹配算法,适用于大规模文本搜索。希望这个解释和示例代码对你理解KMP算法有帮助!如果你有任何问题或需要进一步的解释,请告诉我!
当然可以!让我们通过一个具体的实例来演示KMP算法的工作过程。
示例
假设我们有以下文本串和模式串:
- 文本串:
text = "ABABDABACDABABCABAB"
- 模式串:
pattern = "ABABCABAB"
我们要找到模式串在文本串中的所有出现位置。
步骤 1:构建LPS数组
首先,我们需要构建模式串的LPS数组。
模式串:ABABCABAB
- 计算LPS数组:
lps[0] = 0
(第一个字符没有前缀和后缀)lps[1] = 0
(A
没有相等的前后缀)lps[2] = 1
(AB
的前缀A
和后缀A
相等)lps[3] = 2
(ABA
的前缀AB
和后缀AB
相等)lps[4] = 0
(ABAB
没有相等的前后缀)lps[5] = 1
(ABABC
的前缀A
和后缀A
相等)lps[6] = 2
(ABABCA
的前缀AB
和后缀AB
相等)lps[7] = 3
(ABABCAB
的前缀ABA
和后缀ABA
相等)lps[8] = 4
(ABABCABA
的前缀ABAB
和后缀ABAB
相等)
最终的LPS数组为:
1 | lps = [0, 0, 1, 2, 0, 1, 2, 3, 4] |
步骤 2:进行KMP搜索
接下来我们使用KMP算法进行匹配。
初始化:
i = 0
(文本指针)j = 0
(模式指针)positions = []
(存储匹配位置)
开始匹配:
- 第 1 次比较:
text[0] = 'A'
,pattern[0] = 'A'
→ 匹配,i++
,j++
→i = 1
,j = 1
- 第 2 次比较:
text[1] = 'B'
,pattern[1] = 'B'
→ 匹配,i++
,j++
→i = 2
,j = 2
- 第 3 次比较:
text[2] = 'A'
,pattern[2] = 'A'
→ 匹配,i++
,j++
→i = 3
,j = 3
- 第 4 次比较:
text[3] = 'B'
,pattern[3] = 'B'
→ 匹配,i++
,j++
→i = 4
,j = 4
- 第 5 次比较:
text[4] = 'D'
,pattern[4] = 'C'
→ 不匹配。根据LPS数组,j = lps[3] = 2
,回溯到pattern[2]
。 - 继续比较:
text[4] = 'D'
,pattern[2] = 'A'
→ 不匹配,j = lps[1] = 0
,重置j
。i++
→i = 5
。
- 第 1 次比较:
继续匹配:
- 第 6 次比较:
text[5] = 'A'
,pattern[0] = 'A'
→ 匹配,i++
,j++
→i = 6
,j = 1
- 第 7 次比较:
text[6] = 'B'
,pattern[1] = 'B'
→ 匹配,i++
,j++
→i = 7
,j = 2
- 第 8 次比较:
text[7] = 'A'
,pattern[2] = 'A'
→ 匹配,i++
,j++
→i = 8
,j = 3
- 第 9 次比较:
text[8] = 'C'
,pattern[3] = 'B'
→ 不匹配。根据LPS,j = lps[2] = 1
,回溯到pattern[1]
。 - 继续比较:
text[8] = 'C'
,pattern[1] = 'B'
→ 不匹配,j = lps[0] = 0
,重置j
。i++
→i = 9
。
- 第 6 次比较:
再次匹配:
- 第 10 次比较:
text[9] = 'D'
,pattern[0] = 'A'
→ 不匹配,i++
→i = 10
。 - 第 11 次比较:
text[10] = 'A'
,pattern[0] = 'A'
→ 匹配,i++
,j++
→i = 11
,j = 1
- 第 12 次比较:
text[11] = 'B'
,pattern[1] = 'B'
→ 匹配,i++
,j++
→i = 12
,j = 2
- 第 13 次比较:
text[12] = 'C'
,pattern[2] = 'A'
→ 不匹配,j = lps[1] = 0
,重置j
。i++
→i = 13
。 - 第 14 次比较:
text[13] = 'A'
,pattern[0] = 'A'
→ 匹配,i++
,j++
→i = 14
,j = 1
- 第 15 次比较:
text[14] = 'B'
,pattern[1] = 'B'
→ 匹配,i++
,j++
→i = 15
,j = 2
- 第 16 次比较:
text[15] = 'A'
,pattern[2] = 'A'
→ 匹配,i++
,j++
→i = 16
,j = 3
- 第 17 次比较:
text[16] = 'B'
,pattern[3] = 'B'
→ 匹配,i++
,j++
→i = 17
,j = 4
- 第 18 次比较:
text[17] = 'C'
,pattern[4] = 'C'
→ 匹配,i++
,j++
→i = 18
,j = 5
- 第 19 次比较:
text[18] = 'A'
,pattern[5] = 'A'
→ 匹配,i++
,j++
→i = 19
,j = 6
- 第 20 次比较:
text[19] = 'B'
,pattern[6] = 'B'
→ 匹配,i++
,j++
→i = 20
,j = 7
- 第 21 次比较:
i = 20
,超出文本长度,停止匹配。
- 第 10 次比较:
匹配结果
在整个过程中,我们找到了模式串在文本串中的匹配起始位置:
- 匹配位置:
positions = [10]
总结
- 模式串
"ABABCABAB"
在文本串"ABABDABACDABABCABAB"
中的匹配位置是10
。
这种通过LPS数组的预处理,使得算法能够避免重复比较,提高了效率,特别是在文本较长和模式较短的情况下尤为明显。如果你有其他问题或需要更深入的解释,请随时问我!
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Comments