字符串匹配算法:KMP入门详解
引言:大海捞针的挑战
在计算机科学中,字符串匹配是一个非常基础且重要的课题。它指的是在一个较长的文本串(通常称为主串或目标串 T
)中查找一个较短的模式串(通常称为模式串 P
)的所有出现位置。
这个任务在我们日常生活中无处不在:
* 文本编辑器中的“查找”功能 (Ctrl+F)。
* 搜索引擎在网页内容中查找关键词。
* 生物信息学中查找DNA或蛋白质序列中的特定模式。
* 网络安全中的入侵检测,查找恶意代码签名。
想象一下,主串 T
是浩瀚的大海,模式串 P
是一根针。字符串匹配就是要在大海中找到这根针的所有位置。
最直观的字符串匹配方法是暴力匹配(或称朴素匹配)。它很简单:将模式串的开头与主串的开头对齐,然后逐个字符比较。如果遇到不匹配的字符,就将模式串向右移动一个位置,重新从模式串的开头与主串的新位置对齐,再次进行逐个字符比较,直到模式串与主串的某个部分完全匹配,或者主串遍历完毕。
暴力匹配示例:
假设主串 T = "ABCA BCABC"
,模式串 P = "ABC"
。
-
第一次对齐:
T: A B C A B C A B C
P: A B C
比较T[0]
和P[0]
(A vs A) – 匹配
比较T[1]
和P[1]
(B vs B) – 匹配
比较T[2]
和P[2]
(C vs C) – 匹配
模式串P
完全匹配!在T
的索引 0 处找到一个匹配。 -
第二次对齐: (将模式串向右移动一个位置)
T: A B C A B C A B C
P: A B C
比较T[1]
和P[0]
(B vs A) – 不匹配。 -
第三次对齐: (将模式串向右移动一个位置)
T: A B C A B C A B C
P: A B C
比较T[2]
和P[0]
(C vs A) – 不匹配。 -
第四次对齐: (将模式串向右移动一个位置)
T: A B C A B C A B C
P: A B C
比较T[3]
和P[0]
(A vs A) – 匹配
比较T[4]
和P[1]
(B vs B) – 匹配
比较T[5]
和P[2]
(C vs C) – 匹配
模式串P
完全匹配!在T
的索引 3 处找到一个匹配。
…以此类推,直到主串结束。
暴力匹配的问题:
虽然暴力匹配简单易懂,但在某些情况下效率极低。考虑这样一个例子:
主串 T = "AAAAAAA...AAAAAB"
(100个A,最后1个B)
模式串 P = "AAAAAB"
(5个A,最后1个B)
暴力匹配过程会是这样:
* 第一次对齐:P
对齐 T[0...5]
。比较 T[0]
到 T[4]
都匹配 P[0]
到 P[4]
。在 T[5]
(A) 和 P[5]
(B) 处不匹配。模式串向右移动1位。
* 第二次对齐:P
对齐 T[1...6]
。比较 T[1]
到 T[5]
都匹配 P[0]
到 P[4]
。在 T[6]
(A) 和 P[5]
(B) 处不匹配。模式串向右移动1位。
* …
* 第九十五次对齐:P
对齐 T[94...99]
。比较 T[94]
到 T[98]
都匹配 P[0]
到 P[4]
。在 T[99]
(A) 和 P[5]
(B) 处不匹配。模式串向右移动1位。
* 第九十六次对齐:P
对齐 T[95...100]
。T[95...99]
(AAAAA) 匹配 P[0...4]
(AAAAA)。T[100]
(B) 匹配 P[5]
(B)。完全匹配。
在这个例子中,模式串长度为 m,主串长度为 n。在大多数对齐中,我们都需要比较 m 个字符(或 m-1 个字符)才能发现不匹配,然后模式串只向右移动 1 个位置。这种情况下,总的比较次数接近 O(m * n)。当 m 和 n 都很大时,这将非常慢。
KMP 算法正是为了解决暴力匹配的低效率问题而诞生的。它的核心思想是:在匹配过程中,当发生不匹配时,我们不回溯主串的指针,而是利用已经匹配的部分信息,巧妙地移动模式串的指针,从而避免了大量的重复比较。
KMP 算法的诞生与核心思想
KMP 算法由 Knuth、Morris 和 Pratt 三位学者同时独立提出,因此得名 KMP。
KMP 算法之所以高效,关键在于它避免了在发生不匹配时主串指针的回溯。当 P[j]
与 T[i]
发生不匹配时,我们知道 P[0...j-1]
这一段已经与 T[i-j...i-1]
匹配成功了。KMP 算法利用了 P[0...j-1]
这一段模式串本身的特性来决定模式串应该向右移动多少距离,以便能够继续匹配。
核心洞察: 当 P[j]
与 T[i]
不匹配时,我们知道主串中 T[i-j...i-1]
这段子串等于模式串的 P[0...j-1]
这段前缀。为了继续查找可能的匹配,我们需要将模式串向右移动。新的对齐位置应该使得模式串的某个前缀恰好与主串中 T[i-j...i-1]
的某个后缀对齐,并且这个前缀应该尽可能长,这样我们可以利用之前已经匹配的信息,从新的对齐位置开始比较。
例如,如果在匹配 T[i]
和 P[j]
时发现不匹配,并且 P[0...j-1]
已经匹配成功:
T: ... X X X X T[i] ...
P: ... P[j-1] P[j] ...
(P[0…j-1] 匹配 T[i-j…i-1])
如果我们将模式串向右移动,新的模式串开头应该对齐主串的某个位置 i'
。这意味着 P[0]
应该对齐 T[i']
。并且为了利用之前的匹配信息,我们希望 P[0...k]
(模式串的一个前缀)能够对齐 T[i-k...i-1]
(主串已匹配部分的后缀),其中 T[i-k...i-1]
等于 P[j-k...j-1]
。也就是说,我们希望找到一个最长的 k < j
,使得 P[0...k-1]
等于 P[j-k...j-1]
。
这正是 KMP 算法中一个关键预处理步骤所计算的信息:“部分匹配表”,也称为 “前缀函数” 或 next
数组。
部分匹配表 (前缀函数 π 或 next
数组)
部分匹配表记录了模式串本身的特征,具体来说,对于模式串 P
中的每一个位置 q
,π[q]
的值表示:模式串 P
的前缀 P[0...q]
中,最长的既是真前缀又是真后缀的子串的长度。
这里的“真前缀”是指不包含最后一个字符的前缀,而“真后缀”是指不包含第一个字符的后缀。例如,字符串 “ABABC” 的真前缀有 “A”, “AB”, “ABA”, “ABAB”,真后缀有 “B”, “BC”, “ABC”, “BABC”。对于 “ABABC”,最长的既是真前缀又是真后缀的子串是 “AB”,长度为 2。所以对于索引 4 (即字符 ‘C’),π[4]
= 2。
π[q]
的含义是:如果 P[q]
与主串中的字符失配,并且 P[0...q-1]
已经匹配成功,那么我们可以知道主串的当前位置之前的 q
个字符(即 T[i-q...i-1]
)与 P[0...q-1]
是完全相同的。我们现在需要寻找一个新的对齐方式,使得模式串的某个前缀能够与 T[i-q...i-1]
的某个后缀对齐。根据 π[q-1]
的定义(注意这里是 q-1
,因为失配发生在 P[q]
,意味着 P[0...q-1]
匹配成功),π[q-1]
就是 P[0...q-1]
这个字符串中,最长的既是真前缀又是真后缀的子串的长度。这段长度为 π[q-1]
的子串,既是 P[0...π[q-1]-1]
,也是 P[q-π[q-1]...q-1]
。因为它也是 P[0...q-1]
的后缀,所以它一定等于 T[i-q...i-1]
的对应后缀 T[i-π[q-1]...i-1]
。
这意味着,我们可以将模式串移动到新的位置,使得 P[0...π[q-1]-1]
与 T[i-π[q-1]...i-1]
对齐。新的模式串需要比较的字符将是 P[π[q-1]]
与 T[i]
。如果它们匹配,我们继续比较 P[π[q-1]+1]
与 T[i+1]
;如果不匹配,我们根据 π
表继续进行回溯(在模式串内部)。
所以,当 P[j]
与 T[i]
失配时,且 j > 0
(即不是模式串的第一个字符失配),我们应该将模式串的指针 j
更新为 π[j-1]
。这意味着模式串的下一个需要比较的字符是 P[π[j-1]]
,它将与主串的 T[i]
进行比较。如果 j
已经为 0 (模式串的第一个字符就失配),则只能将主串指针 i
向前移动一位。
计算部分匹配表 (π
数组 或 next
数组):
计算 π
数组本身也是一个模式匹配的过程,只不过是模式串与它自身的前缀进行匹配。
设模式串 P
的长度为 m
。π
数组的大小为 m
。
我们从 π[0]
开始计算。按照定义,长度为 1 的前缀 (P[0]
) 没有真前缀和真后缀,所以 π[0] = 0
。
我们使用两个指针:i
(当前计算 π
值的索引,从 1 到 m-1) 和 length
(已知的最长前缀/后缀的长度,也是 π[i-1]
计算完成后可能用到的长度)。
初始化 π[0] = 0
,length = 0
,i = 1
。
遍历 i
从 1 到 m-1
:
1. 比较 P[i]
和 P[length]
。
2. 如果 P[i]
== P[length]
: 说明 P[0...length]
的下一个字符 P[length]
与 P[i]
匹配,那么 P[0...length]
是 P[0...i]
的一个前缀,并且 P[i-length...i]
是 P[0...i]
的一个后缀。由于 P[0...length-1]
已经是 P[0...i-1]
最长的公共前后缀,现在 P[length]
== P[i]
, 那么 P[0...length]
就是 P[0...i]
最长的公共前后缀。所以,将 length
增加 1,并设置 π[i] = length
。然后继续下一个 i
。
3. 如果 P[i]
!= P[length]
: 说明当前的 length
不能继续扩展了。我们需要寻找一个更短的长度 length'
,使得 P[0...length'-1]
是 P[0...i-1]
的一个公共前后缀,并且 P[length']
能够与 P[i]
匹配。根据 π
数组的定义,π[length-1]
就是 P[0...length-1]
这个字符串中,最长的既是真前缀又是真后缀的长度。所以,我们将 length
更新为 π[length-1]
,然后继续比较 P[i]
和 P[length]
。这个过程是一个循环,直到 length
变为 0。
* 如果在 length > 0
的情况下,我们设置 length = π[length-1]
,然后回到步骤 1(比较 P[i]
和新的 P[length]
)。
* 如果 length
已经变为 0,并且 P[i]
仍然不等于 P[0]
,说明 P[0...i]
没有长度大于 0 的公共前后缀,设置 π[i] = 0
。然后将 i
增加 1,继续下一个 i
的计算。
* 如果 length
已经变为 0,并且 P[i]
等于 P[0]
,说明 P[0]
是 P[0...i]
最长的长度为 1 的公共前后缀,设置 π[i] = 1
,并设置 length = 1
。然后将 i
增加 1,继续下一个 i
的计算。
计算 π
数组示例:
设模式串 P = "ABACABABC"
,长度 m = 9
。
π
数组大小为 9。
π[0] = 0
(约定或根据定义)
i = 1
: P[1] = 'B'
, length = 0
, P[length] = P[0] = 'A'
. 'B' != 'A'
. length
已经是 0。所以 π[1] = 0
. length
仍然是 0.
i = 2
: P[2] = 'A'
, length = 0
, P[length] = P[0] = 'A'
. 'A' == 'A'
. 匹配。length
变为 0 + 1 = 1
. π[2] = 1
.
i = 3
: P[3] = 'C'
, length = 1
, P[length] = P[1] = 'B'
. 'C' != 'B'
. length > 0
. length
更新为 π[length-1] = π[1] = 0
. 现在 length = 0
. P[3] = 'C'
, P[length] = P[0] = 'A'
. 'C' != 'A'
. length
仍为 0. 所以 π[3] = 0
. length
仍然是 0.
i = 4
: P[4] = 'A'
, length = 0
, P[length] = P[0] = 'A'
. 'A' == 'A'
. 匹配。length
变为 0 + 1 = 1
. π[4] = 1
.
i = 5
: P[5] = 'B'
, length = 1
, P[length] = P[1] = 'B'
. 'B' == 'B'
. 匹配。length
变为 1 + 1 = 2
. π[5] = 2
.
i = 6
: P[6] = 'A'
, length = 2
, P[length] = P[2] = 'A'
. 'A' == 'A'
. 匹配。length
变为 2 + 1 = 3
. π[6] = 3
.
i = 7
: P[7] = 'B'
, length = 3
, P[length] = P[3] = 'C'
. 'B' != 'C'
. length > 0
. length
更新为 π[length-1] = π[2] = 1
. 现在 length = 1
. 继续比较 P[7]
和 P[length] = P[1]
. P[7] = 'B'
, P[1] = 'B'
. 'B' == 'B'
. 匹配。length
变为 1 + 1 = 2
. π[7] = 2
.
i = 8
: P[8] = 'C'
, length = 2
, P[length] = P[2] = 'A'
. 'C' != 'A'
. length > 0
. length
更新为 π[length-1] = π[1] = 0
. 现在 length = 0
. 继续比较 P[8]
和 P[length] = P[0]
. P[8] = 'C'
, P[0] = 'A'
. 'C' != 'A'
. length
仍为 0. 所以 π[8] = 0
. length
仍然是 0.
计算完成。π
数组为 [0, 0, 1, 0, 1, 2, 3, 2, 0]
。
索引 q |
字符 P[q] |
前缀 P[0...q] |
真前缀 | 真后缀 | 最长公共前后缀 | 长度 π[q] |
---|---|---|---|---|---|---|
0 | A | A | (无) | (无) | (无) | 0 |
1 | B | AB | A | B | (无) | 0 |
2 | A | ABA | A, AB | A, BA | A | 1 |
3 | C | ABAC | A, AB, ABA | C, AC, BAC | (无) | 0 |
4 | A | ABACA | A, AB, ABA, ABAC | A, CA, ACA, BACA | A | 1 |
5 | B | ABACAB | A, AB, ABA, ABAC, ABACA | B, AB, CAB, ACAB, BACAB | AB | 2 |
6 | A | ABACABA | A,…ABACAB | A,…ACABA | ABA | 3 |
7 | B | ABACABAB | A,…ABACABA | B,…CABAB | AB | 2 |
8 | C | ABACABABC | A,…ABACABAB | C,…ABABC | (无) | 0 |
这个 π
数组正是 KMP 算法进行高效匹配的关键。它告诉我们在模式串的某个位置失配后,模式串的下一个应该比较的字符是哪一个。
KMP 匹配算法
有了部分匹配表 π
,KMP 匹配过程就相对简单了。
使用两个指针:
* i
: 主串 T
的当前比较位置(从 0 到 n-1)。
* j
: 模式串 P
的当前比较位置(从 0 到 m-1)。
初始化 i = 0
, j = 0
.
遍历主串 T
:
当 i < n
:
1. 如果 P[j]
== T[i]
: 字符匹配。两个指针都向前移动一位:i++
, j++
.
2. 如果 j == m
: 说明模式串 P
已经完全匹配!一个匹配项在主串 T
的 i - m
位置找到。为了寻找下一个可能的匹配,我们不能简单地重置 j = 0
并从 i
开始。我们知道 P[0...m-1]
匹配了 T[i-m...i-1]
。我们需要找到 P
的最长公共前后缀,其长度是 π[m-1]
。这个长度为 π[m-1]
的前缀 P[0...π[m-1]-1]
也与 T[i-m...i-m+π[m-1]-1]
相等,并且这个子串也等于 P[m-π[m-1]...m-1]
。所以,我们可以将模式串移动到新的位置,使得 P[0]
对齐到 T[i-π[m-1]]
。在算法实现上,这相当于将模式串的指针 j
直接更新为 π[m-1]
,然后继续比较 P[j]
和 T[i]
(此时 i
已经指向匹配结束的后一个字符,无需回溯)。
3. 如果 P[j]
!= T[i]
(失配) 且 j > 0
: 说明 P[0...j-1]
已经匹配成功,但 P[j]
与 T[i]
不匹配。根据 π
数组的定义,我们需要将模式串的指针 j
更新为 π[j-1]
。这个新的 j
值表示模式串中下一个应该与 T[i]
进行比较的字符的位置。主串指针 i
不变。
4. 如果 P[j]
!= T[i]
(失配) 且 j == 0
: 说明模式串的第一个字符就与主串当前字符不匹配。这时只能将主串指针 i
向前移动一位:i++
. 模式串指针 j
保持 0 不变。
KMP 匹配示例:
设主串 T = "ABACABABCABA"
,模式串 P = "ABACABABC"
。
模式串 P
的 π
数组之前已经计算出来了:[0, 0, 1, 0, 1, 2, 3, 2, 0]
。
初始化 i = 0
, j = 0
.
T 索引 (i) | T[i] | P 索引 (j) | P[j] | 比较结果 | 动作 | i (next) | j (next) | π[j-1] (if j>0) | 备注 |
---|---|---|---|---|---|---|---|---|---|
0 | A | 0 | A | 匹配 | i++ , j++ |
1 | 1 | ||
1 | B | 1 | B | 匹配 | i++ , j++ |
2 | 2 | ||
2 | A | 2 | A | 匹配 | i++ , j++ |
3 | 3 | ||
3 | C | 3 | C | 匹配 | i++ , j++ |
4 | 4 | ||
4 | A | 4 | A | 匹配 | i++ , j++ |
5 | 5 | ||
5 | B | 5 | B | 匹配 | i++ , j++ |
6 | 6 | ||
6 | A | 6 | A | 匹配 | i++ , j++ |
7 | 7 | ||
7 | B | 7 | B | 匹配 | i++ , j++ |
8 | 8 | ||
8 | C | 8 | C | 匹配 | i++ , j++ |
9 | 9 | ||
9 | j == m | 匹配成功!位置 9-9=0。 j = π[m-1]=π[8]=0 | 9 | 0 | π[8]=0 | 模式串完全匹配!位置 0。j回溯到π[8]=0 | |||
9 | A | 0 | A | 匹配 | i++ , j++ |
10 | 1 | 从新的j位置继续比较 T[9]和P[0] | |
10 | B | 1 | B | 匹配 | i++ , j++ |
11 | 2 | ||
11 | A | 2 | A | 匹配 | i++ , j++ |
12 | 3 | ||
12 | \0 | 3 | C | i == n | 主串结束 |
在这个例子中,我们在主串索引 0 处找到了一个匹配。主串遍历完毕。
注意在 i=8, j=8
匹配后,j
变为 9,等于模式串长度。我们找到了一个匹配。然后我们将 j
更新为 π[m-1] = π[8] = 0
,表示找到匹配后模式串的新对齐位置。i
保持在 9。下一次循环开始时,我们会比较 T[9]
和 P[0]
。
让我们看一个失配的例子。假设 T = "ABACABAT"
,P = "ABACABAB"
。
P
的 π
数组:[0, 0, 1, 0, 1, 2, 3, 2]
(长度 m=8)。
初始化 i = 0
, j = 0
.
T 索引 (i) | T[i] | P 索引 (j) | P[j] | 比较结果 | 动作 | i (next) | j (next) | π[j-1] (if j>0) | 备注 |
---|---|---|---|---|---|---|---|---|---|
0 | A | 0 | A | 匹配 | i++ , j++ |
1 | 1 | ||
1 | B | 1 | B | 匹配 | i++ , j++ |
2 | 2 | ||
2 | A | 2 | A | 匹配 | i++ , j++ |
3 | 3 | ||
3 | C | 3 | C | 匹配 | i++ , j++ |
4 | 4 | ||
4 | A | 4 | A | 匹配 | i++ , j++ |
5 | 5 | ||
5 | B | 5 | B | 匹配 | i++ , j++ |
6 | 6 | ||
6 | A | 6 | A | 匹配 | i++ , j++ |
7 | 7 | ||
7 | T | 7 | B | 不匹配 | j > 0 , j = π[j-1] |
7 | 2 | π[6]=3 -> π[2]=1 | P[7] != T[7]。 j回溯到 π[7-1]=π[6]=3? 错了,应该是 j回溯到 π[j-1]=π[6]=3。哦,不对,π[6]是 P[0…6]的 next,失配发生在 P[7]。应该看 P[0…6]的最长前后缀,其长度是 π[6]=3。所以新的j应该是 3。 |
修正:当 P[j] 与 T[i]失配时,我们知道 P[0…j-1] 匹配了 T[i-j…i-1]。我们需要找到 P[0…j-1]的最长公共前后缀的长度 k = π[j-1]。然后将模式串移动,使得 P[0…k-1] 对齐 T[i-k…i-1]。这时新的匹配点是 P[k] 与 T[i]。所以模式串指针直接更新为 k。 | |||||||||
7 | T | 7 | B | 不匹配 | j > 0 , j = π[j-1] |
7 | 3 | π[6]=3 | P[7] != T[7]。 j回溯到 π[7-1]=π[6]=3。 |
7 | T | 3 | C | 不匹配 | j > 0 , j = π[j-1] |
7 | 0 | π[2]=1 | 新的 j=3,比较 T[7] 和 P3,不匹配。j回溯到 π[3-1]=π[2]=1。 |
7 | T | 0 | A | 不匹配 | j == 0 , i++ |
8 | 0 | 新的 j=1,比较 T[7] 和 P1,不匹配。j回溯到 π[1-1]=π[0]=0。现在 j=0。比较 T[7] 和 P0,不匹配。j==0,i++。 | |
8 | \0 | 0 | A | i == n | 主串结束 |
这个例子展示了失配时 j
如何根据 π
数组回溯,而 i
保持不变。
KMP 算法实现 (Python 示例)
“`python
def compute_prefix_function(pattern):
“””
计算模式串的部分匹配表(前缀函数 π 或 next 数组)
Args:
pattern: 模式串 P
Returns:
π 数组 (list of int)
“””
m = len(pattern)
pi = [0] * m # 初始化π数组,长度为 m
length = 0 # length 记录当前计算位置 i 的最长公共前后缀的长度
# π[0] 始终为 0,从索引 1 开始计算
i = 1
while i < m:
# Case 1: 当前字符 pattern[i] 和 pattern[length] 匹配
if pattern[i] == pattern[length]:
length += 1
pi[i] = length
i += 1
# Case 2: 不匹配
else:
# Case 2.1: length > 0,根据 π 数组回溯到前一个最长公共前后缀的长度
# pattern[length] 是当前不匹配的字符,我们回到其前一个最长公共前后缀的末尾
# 也就是将 length 更新为 pi[length-1]
if length != 0:
length = pi[length - 1]
# 注意:这里不增加 i,因为我们需要用新的 length 值(对应 pattern 的新前缀)
# 再次尝试与 pattern[i] 匹配
# Case 2.2: length == 0, pattern[i] 和 pattern[0] 不匹配
# 说明 pattern[0...i] 没有长度大于 0 的公共前后缀
else:
pi[i] = 0
i += 1
return pi
def kmp_search(text, pattern):
“””
使用 KMP 算法在文本串中查找模式串
Args:
text: 主串 T
pattern: 模式串 P
Returns:
匹配成功的起始索引列表
“””
n = len(text)
m = len(pattern)
if m == 0:
return list(range(n + 1)) # 空模式串匹配所有位置
if m > n:
return [] # 模式串比主串长,不可能匹配
pi = compute_prefix_function(pattern)
match_positions = [] # 记录匹配成功的起始索引
i = 0 # 主串指针
j = 0 # 模式串指针
while i < n:
# Case 1: 当前字符 text[i] 和 pattern[j] 匹配
if text[i] == pattern[j]:
i += 1
j += 1
# Case 2: 模式串指针 j 已经到达模式串末尾,说明找到一个匹配
if j == m:
# 找到一个匹配,起始位置在 text 的 i - m
match_positions.append(i - m)
# 为了寻找下一个匹配,模式串指针需要根据 pi 数组回溯
# 回溯到 pi[m-1] 的位置,表示模式串的最长公共前后缀长度
# pattern[0...pi[m-1]-1] 已经匹配了 text[i-m...i-m+pi[m-1]-1]
# 下一个需要比较的模式串字符是 pattern[pi[m-1]]
j = pi[m - 1]
# Case 3: 当前字符不匹配,且模式串指针 j > 0
elif i < n and text[i] != pattern[j]:
# 根据 pi 数组,将模式串指针回溯到 pi[j-1]
# text[i] 将与 pattern[pi[j-1]] 再次比较
if j != 0:
j = pi[j - 1]
# Case 4: 当前字符不匹配,且模式串指针 j == 0
# 说明模式串的第一个字符就不匹配,主串指针向前移动一位
else:
i += 1
return match_positions
示例使用
text = “ABACABABCABA”
pattern = “ABACABABC”
positions = kmp_search(text, pattern)
print(f”文本串: {text}”)
print(f”模式串: {pattern}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern)}”)
print(f”匹配位置: {positions}”) # 期望输出: [0]
text2 = “AAAAAAAAB”
pattern2 = “AAAAB”
positions2 = kmp_search(text2, pattern2)
print(f”\n文本串: {text2}”)
print(f”模式串: {pattern2}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern2)}”)
print(f”匹配位置: {positions2}”) # 期望输出: [4]
text3 = “ABABABAB”
pattern3 = “ABAB”
positions3 = kmp_search(text3, pattern3)
print(f”\n文本串: {text3}”)
print(f”模式串: {pattern3}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern3)}”)
print(f”匹配位置: {positions3}”) # 期望输出: [0, 2, 4]
text4 = “THIS IS A TEST TEXT”
pattern4 = “TEST”
positions4 = kmp_search(text4, pattern4)
print(f”\n文本串: {text4}”)
print(f”模式串: {pattern4}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern4)}”)
print(f”匹配位置: {positions4}”) # 期望输出: [10]
“`
关于 j = pi[m-1]
的解释:
当 j == m
时,意味着 pattern[0...m-1]
与 text[i-m...i-1]
匹配成功。我们找到了一个匹配。为了寻找下一个匹配,模式串需要向右移动。新的模式串开头应该对齐 text
中某个位置,使得模式串的某个前缀与 text[i-m...i-1]
的某个后缀对齐。text[i-m...i-1]
正是 pattern[0...m-1]
。所以我们是在寻找 pattern[0...m-1]
的最长公共前后缀,其长度为 pi[m-1]
。这个长度为 k = pi[m-1]
的前缀 pattern[0...k-1]
等于其后缀 pattern[m-k...m-1]
。当我们把模式串移动使得 pattern[0...k-1]
对齐 text[i-k...i-1]
(也就是 pattern[m-k...m-1]
) 时,模式串的下一个待比较字符是 pattern[k]
,它将与 text[i]
对齐(因为 text[i]
是上一个匹配结束的后一个字符)。所以,在找到一个匹配后,将 j
更新为 pi[m-1]
是正确的做法。
关于 j = pi[j-1]
的解释:
当 text[i] != pattern[j]
且 j > 0
时,意味着 pattern[0...j-1]
与 text[i-j...i-1]
已经匹配。我们知道 text[i-j...i-1]
等于 pattern[0...j-1]
。现在失配发生在 text[i]
和 pattern[j]
。我们需要将模式串向右移动,使得模式串的某个前缀能够与 text[i-j...i-1]
的某个后缀对齐。text[i-j...i-1]
就是 pattern[0...j-1]
。所以我们寻找 pattern[0...j-1]
的最长公共前后缀,其长度为 k = pi[j-1]
。这段长度为 k
的前缀 pattern[0...k-1]
也是 pattern[0...j-1]
的后缀。新的对齐位置会使得 pattern[0...k-1]
对齐 text[i-k...i-1]
(也就是 pattern[j-k...j-1]
)。此时模式串中应该与 text[i]
比较的字符是 pattern[k]
。因此,将模式串指针 j
直接更新为 k = pi[j-1]
是正确的。主串指针 i
不变,因为 text[i]
还没有被参与到有效的匹配中,需要用新的 pattern[j]
来尝试匹配它。
KMP 算法的复杂度分析
KMP 算法分为两个阶段:计算部分匹配表和匹配过程。
-
计算部分匹配表 (
compute_prefix_function
):- 模式串长度为
m
。 - 指针
i
从 1 遍历到m-1
,总共进行m-1
次外层循环。 - 在每次循环中,如果
pattern[i]
与pattern[length]
匹配,length
增加 1。i
增加 1。 - 如果
pattern[i]
与pattern[length]
不匹配:- 如果
length > 0
,length
被更新为pi[length-1]
。这个操作会使length
减小。 - 如果
length == 0
,i
增加 1。
- 如果
- 关键在于理解
length
的变化。在整个计算过程中,length
的值单调不减,每次匹配成功时增加 1,总共最多增加m-1
次。当不匹配时,length
会减小(或保持 0),这个减小操作是基于pi
数组的,length
的总减小量不会超过它之前的总增加量。因此,虽然有内层的while length != 0
回溯,但每个字符pattern[i]
最多导致length
增加一次,也最多导致length
减少有限次(因为length
不能减到负数,总减小量受限于总增加量)。所以,计算pi
数组的总时间复杂度是 O(m)。
- 模式串长度为
-
匹配过程 (
kmp_search
):- 主串长度为
n
,模式串长度为m
。 - 主串指针
i
从 0 遍历到n-1
。i
只会向前移动,从不回溯。i
最多移动n
次。 - 模式串指针
j
:- 匹配时,
j
增加 1。j
的值不会超过m
。 - 失配时,如果
j > 0
,j
根据pi[j-1]
减小。如果j == 0
,i
增加 1。 - 匹配成功后,
j
根据pi[m-1]
减小。
- 匹配时,
- 指针
i
至少移动n
次 (从 0 到 n-1)。每次移动i
时,i
增加 1。 - 指针
j
每次成功匹配时增加 1。总共成功匹配次数加上失配回溯次数构成了总比较次数。 - 考虑
i + j
的变化。每次成功匹配时i
和j
都增加 1,所以i+j
增加 2。失配且j > 0
时,j
减小,i
不变,i+j
减小。失配且j == 0
时,i
增加 1,j
不变,i+j
增加 1。成功匹配后j
减小,i
不变,i+j
减小。 - 更直观的分析:主串指针
i
永远不会回溯,它从头走到尾最多n
步。模式串指针j
只会在匹配成功时增加,或者在失配时根据pi
数组减小。j
的最大值是m
。对于主串中的每一个字符T[i]
,它最多与模式串中的某个字符P[j]
进行一次匹配成功的比较(i++
,j++
),也最多与模式串中的某个字符P[j]
进行有限次匹配失败的比较(j
回溯但i
不变)。因为j
的回溯总是利用pi
数组将j
移动到更小的值,而j
的值始终非负,所以j
回溯的总次数是有限的。总的比较次数不会超过 O(n + m)。 - 因此,匹配过程的总时间复杂度是 O(n)。
- 主串长度为
总时间复杂度: 计算 π
数组 O(m) + 匹配过程 O(n) = O(n + m)。
空间复杂度: 需要额外 O(m) 的空间来存储 π
数组。
与暴力匹配的 O(m*n) 相比,KMP 算法的时间复杂度是线性的 O(n + m),这在处理大规模文本时是巨大的优势。
总结与展望
KMP 算法是一个经典的字符串匹配算法,其核心思想是利用模式串本身的结构信息(通过预计算部分匹配表 π
)来避免在失配时进行不必要的主串回溯。这使得 KMP 算法能够在 O(n + m) 的时间复杂度内完成字符串匹配,达到了理论最优(因为至少需要读取主串和模式串的所有字符)。
虽然 KMP 算法的 π
数组计算和匹配过程对于初学者来说可能有点抽象和难以理解,特别是 j = pi[j-1]
和 j = pi[m-1]
这两个关键的模式串指针移动步骤。理解其背后的逻辑(利用已匹配部分的公共前后缀信息来确定下一次比较的位置)是掌握 KMP 的关键。多画图,多模拟算法运行过程,是理解 KMP 的有效方法。
KMP 算法是许多更高级字符串算法(如 Rabin-Karp, Boyer-Moore 等)的基础,也是理解算法设计中“预处理”和“利用已知信息”思想的优秀案例。掌握 KMP 算法是学习更复杂文本处理和算法的良好起点。
希望这篇入门文章能帮助你迈出理解 KMP 算法的第一步!