字符串匹配

This article is a study note on Introduction to Algorithms.

定义

顾名思义，在一个目标串中寻找是否出现模板串的过程，为字符串匹配。

算法 预处理时间 匹配时间
朴素算法 00 O((n−m+1)m)Ο((n-m+1)m)
Rabin-Karp Θ(m)\Theta(m) O((n−m+1)m)Ο((n-m+1)m)
有限自动机算法 $Ο(m \Sigma
Knuth-Morris-Pratt Θ(m)\Theta(m) Θ(n)\Theta(n)

朴素字符串匹配算法

最简单直观的算法，又叫做BF(Brute Force)算法。两层循环，逐一比较目标串与模式串之间的每一个字符是否匹配。

伪代码
1
2
3
4
5
6
NAIVE-STRING-MATCHER(T,P) 
n = T.length 
m = P.length 
for s = O to n — m 
	if P[1..m] == T[s+1.. s+m]
 	print "Pattern occurs with shift" s
时间复杂度

在最坏情况下，朴素字符串匹配算法运行时间为O((n-m+l)m)。例如，在考察文本字符串 a^n^（一串由n个a组成的字符串）和模式 a^m^ 时，对偏移s的n-m+1个可能值中的每一个，在第4行中比较相应字符的隐式循环必须执行m次来确定偏移的有效性。因此，最坏情况下的运行时间是Ο((n-m+1)m).由于不需要预处理，朴素字符串匹配算法运行时间即为其匹配时间。

Rabin-Karp 算法

RK算法的核心思想就是通过计算模式串的哈希值与文本串中每个长度等于模式串的子串的哈希值进行比较，从而减少匹配的次数。当然，为了节省资源，哈希函数一般是由自己编写。同时，为了避免哈希碰撞产生的误判，哈希值相同的字符串还需要进行一次匹配验证。

一般情况下，算法的哈希函数会这么实现：取一个基数d（一般是字符串中出现的字符种类个数）和素数q，将每一个字符与1~d中的一个数匹配，此时字符串S可以视为一串数。将S转化为d+1进制的数，通常这个数会比较大，将其mod q(如：1e9+7) 得到一个较小的数，取这个数作为字符串的哈希值。

字符串哈希需要注意一下发生碰撞的概率。当我们对M取模时，则在计算根号M次时，就极易发生碰撞(生日攻击)。在进行n = 1e6 次计算，M = 1e9+7 ，则有1/1000的概率会发生碰撞。实际上在算法竞赛中，单哈希已经不安全了 ，例如题目 Hash Killer 2 就是让你构造一组数据去卡住M = 1e9+7 的哈希。所以常见的方法是双哈希，即取M1，M2 两个不同的模数，这样值域就被扩展到了M1*M2上，极大减少了实际上可以卡住的构造方法。

伪代码

输入是文本T, 模式P, 使用基数d和素数q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
RABIN-KARP-MATCHER(T,P,d,q) 
n = T.length 
m = P.length 
h = d^(m-1) mod q 
p = 0
t_0 = O
for i = 1 to m			// preprocessing 
	p = (d*p+P[i]） mod q 
	t_0 = (d*t_0+T[i]) mod q 
for s = 0 to n-m		// matching 
    if p == t, 
        if P[1..m] == T[s+1..s十m]
        print"Pattern occurs with shift" s 
    if s < n-m 
    	t_(s+1) = (d*(t_s - T[s+1]*h) + T[s+m+1]) mod q

RABIN-KARP-MATCHER 执行过程如下。所有的字符都假设是d进制的数字。仅为了说明的清楚，给t添加了下标，去除所有下标不会影响程序运行。第 4 行初始化m位窗口中高位上的值h。第 5~9 行计算出P[1..m] mod q 的值p, 计算出 T[1.. m] mod q的值 t~0~ 。第 10~15 行的 for 循环迭代便利了所有可能的偏移s, 保持如下的不变量：

​ 第 11 行无论何时执行，都有 ts=T[s+1…s+m]mod  qt_s = T[s+1\dots s+m] \mod q

如果在第 11 行中有p=tsp=t_s(一个“命中点")那么在第 12 行检测是否 P[1…m] = T[s+1…s+m], 用以排除它是伪命中点的可能性。第 13 行打印出所有找到的有效偏移。如果s < n-m(在第14行检测)，则至少再执行一次for循环，这时首先执行第 15 行以保证再次执行到第 11 行时循环不变式依然成立。第 14 行直接利用等式

ts+1=(d(ts−T[s+1]h)+T[s+m+1])mod  qt_{s+1} = (d(t_s-T[s+1]h) + T[s+m+1]) \mod q

就可以在常数时间内由 tsmod  qt_s\mod q 的值计算出 ts+1mod  qt_{s+1}\mod q的值。

复杂度

RABIN-KARP-MATCHER的预处理时间为 Θ(m)\Theta(m), 在最坏情况下，它的匹配时间是 ,O((n−m+1)m)Ο((n-m+1)m) 因为Rabin-Karp算法和朴素字符串匹配算法一样，对每个有效偏移进行显式验证。如果P=a^m^并且T=a^n^, 由于在n—m+1个可能的偏移中每一个都是有效的，则验证所需的时间为 O((n−m+1)m)Ο((n-m+1)m)。

当然，在一般情况下，算法所需的时间并不会达到最大。除非特地构造，每一个偏移都有效的概率并不比彩票实现财富自由的几率高。我们可以通过严谨的数学证明得到这种算法的期望运行时间：(别问我，我不会)

O(n)+O(m(v+n/q))O(n)+O(m(v+n/q))

其中v是有效偏移量。如果v=O(1)v=O(1)并且q≥mq\geq m, 则这个算法的运行时间是O(n)O(n)。也就是说，如果期望的有效偏移量很少(O(1)O(1)) ，而选取的素数q大于模式的长度，则可以估计Rabin-Karp算法的匹配时间为 O(n+m)O(n+m), 由于m<=n, 这个算法的期望匹配时间是O(n)O(n)。

利用有限自动机进行字符串匹配

复杂且效率不如KMP，过。（其实是没搞明白，数学证明好多）

Knuth-Morris-Pratt 算法

KMP算法通过计算字符串子串的最长公共前后缀，从而减少字符串匹配次数，达到提高效率的目的。

python代码

伪代码太抽象了，还不如直接写出来。代码段由GPT-4o生成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
def compute_lps(pattern):
    """
    计算模式字符串的最长前缀后缀数组（LPS数组）。
    LPS数组表示模式字符串中每个前缀的最长前缀后缀的长度。
    有些（应该说很多）时候被叫做NEXT数组。
    不更改的原因是偷懒（bushi

    参数:
    pattern (str): 模式字符串

    返回:
    list: 模式字符串的LPS数组
    """
    lps = [0] * len(pattern)  # 初始化LPS数组，长度与模式字符串相同，初始值为0
    length = 0  # 记录最长前缀后缀的长度
    i = 1  # 从第二个字符开始计算LPS值

    while i < len(pattern):
        if pattern[i] == pattern[length]: # 使用双指针比较
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1] # 让前指针回到可能出现匹配字符串的位置继续比较
            else:
                lps[i] = 0 # 所有位置都不符合，没有公共串
                i += 1

    return lps

def kmp_search(text, pattern):
    """
    使用KMP算法在文本字符串中搜索模式字符串的位置。

    参数:
    text (str): 文本字符串
    pattern (str): 模式字符串

    返回:
    list: 模式字符串在文本字符串中的起始索引列表
    """
    lps = compute_lps(pattern)  # 计算模式字符串的LPS数组
    result = []  # 存储匹配的起始索引
    i = 0  # 文本字符串的索引
    j = 0  # 模式字符串的索引

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == len(pattern):
            result.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return result

# 测试样例1
text1 = "AAABABAAABABAAABABAA"
pattern1 = "ABABAAABABAA"
print("文本字符串：", text1)
print("模式字符串：", pattern1)
print("匹配的起始索引：", kmp_search(text1, pattern1))
print("lps数组", compute_lps(pattern1))

"""
运行结果：
文本字符串： AAABABAAABABAAABABAA
模式字符串： ABABAAABABAA
匹配的起始索引： [2, 8]
lps数组 [0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5, 6]
"""

正确性解释（粗）

1. LPS数组的正确性

定义：对于模式字符串 $ P=P[0]P[1]…P[m−1] $，LPS数组的值 LPS[i]LPS[i] 是使得 P[0]P[1]…P[LPS[i]−1]P[0]P[1]…P[LPS[i]−1] 等于 P[i−LPS[i]+1]P[i−LPS[i]+2]…P[i]P[i−LPS[i]+1]P[i−LPS[i]+2]…P[i]的最大值。

证明：

  • 初始时， LPS[0]=0LPS[0]=0，因为没有比自身更短的前缀。
  • 对于每个i从1到m−1：
    • 如果 $ P[i]==P[length]$，那么 LPS[i]=length+1LPS[i]=length+1，即新增的字符与之前最长共同前后缀的下一个字符一致，共同前后缀的长度增加1， length+1length+1，继续比较下一个字符。
    • 否则，将 lengthlength 设置为 LPS[length−1]LPS[length−1]，然后继续比较。当发生不匹配时，我们将前指针往回移动一位，并且取其LPS的值LPS[length−1]LPS[length−1]赋值给 lengthlength，意味着 下一次循环会从该位的最长共同前后缀的下一位开始比较 。由于我们可以确定后指针的前 length赋值前length_{赋值前} 项相同，所以前字符串的最大相同前缀和后字符串的最大相同后缀相同。如果前字符串的最长共同前后缀的下一位与当前后指针所指字符相同，则共同前后缀的长度增加1，继续比较下一位；如果不同，则重复上述步骤。

注意！在这段代码中，LPS[i]的值代表了最长公共前后缀的长度，而P[i]是在字符串上第 i+1 位的字符（代码中字符串从[0]开始储存）。因此即P[LPS[l-1]]代表了 找到的最长共前子串的后一个 字符。这就是代码中没有出现很多模板中采用的P[l+1]的原因。这种写法保持了代码的简洁性（不需要预处理字符串、更少的计算符号），同时也带来了一些理解阻碍。不过在这种并不会毁坏代码可读性的情况下，更加简洁优雅的代码显然是应该被采纳的写法。

2. 主循环中的正确性

KMP算法的主循环通过模式字符串PP和文本字符串TT的匹配过程进行描述：

定义：

  • $i 是文本字符串是文本字符串T$的当前索引。
  • jj是模式字符串的PP当前索引。

主循环步骤：

  1. 如果$ P[j] == T[i]，则，则i 和和j$同时增加1。
  2. 如果jj达到mm，表示匹配成功，将匹配的起始索引加入结果列表，然后通过$ LPS[j-1]$继续寻找下一个匹配。
  3. 如果i<ni < n且P[j]≠T[i]P[j] \neq T[i]：
    • 如果j≠0j \neq 0，则设置jj为$ LPS[j-1]，并且不增加，并且不增加i $。
    • 否则，仅增加$i $。
证明匹配过程不回溯

假设在$ T[i] $处发生不匹配：

  • jj是模式字符串中的当前位置。
  • 由于$ j = LPS[j-1]，这意味着我们已经匹配了，这意味着我们已经匹配了P[0]P[1]…P[LPS[j-1]-1]$。
  • 因为 $ LPS[j-1]$是 P[0]P[1]...P[LPS[j−1]−1]P[0]P[1]...P[LPS[j-1]-1] 的最长前缀后缀，所以在$ T[i] $处发生不匹配时，模式字符串中的前缀已经被考虑。

复杂度

时间复杂度

KMP算法主要包括两个步骤：

  1. 计算模式字符串的LPS（最长前缀后缀）数组。

计算LPS数组的时间复杂度为 O(m)O(m)，其中m是模式字符串的长度。具体分析如下：

  • 初始化LPS数组需要 O(m)O(m) 时间。
  • 在计算过程中，每个字符最多被访问两次（一次用于匹配，一次用于跳转），因此整体时间复杂度为 O(m)O(m)。
  1. 使用LPS数组在文本字符串中进行模式匹配。

使用LPS数组进行模式匹配的时间复杂度为O(n)O(n)，其中n是文本字符串的长度。具体分析如下：

  • 每个字符最多被访问两次（一次用于匹配，一次用于跳转），因此整体时间复杂度为 O(n)O(n)。

将两个步骤的时间复杂度相加，总时间复杂度为：

O(m)+O(n)=O(n+m)O(m) + O(n) = O(n + m)

空间复杂度

KMP算法的空间复杂度主要由存储LPS数组的空间决定。

  • LPS数组的长度为 (m)，因此需要 (O(m)O(m)) 的空间。
  • 除此之外，算法本身只使用了常数级别的额外空间（若干个变量）。

总空间复杂度为：

O(m)O(m)