字符串匹配(一)

字符串匹配问题,就是给定一个文本串和一个模式串,找出模式串在文本串中出现的首位置。

一般来说,有暴力算法,KMP 算法,BM 算法,Horspool 算法,Sunday 算法。这些算法用于单模式匹配,也就是说只需要找出模式串在文本串中首次出现的首位置即可。当然还有多模式匹配算法,比如 AC 算法,它可以在文本串中查找出所有模式串(因为模式串中文本串可能多次出现)的首位置。这里只介绍单模式匹配算法。

1 暴力算法

暴力算法很简单,在某一次匹配中匹配失败时,只要将模式串向右移动一个字符,然后进行下一次匹配。而且每次匹配开始时,都是从模式串的首字符开始。

值得注意的是结束条件。如果在某一次匹配过程中,模式字符串的所有字符都被扫描过了,则表示匹配成功,返回文本串中匹配成功的字符串的首位置的下标;如果在某一次的匹配过程中,文本串中某个字符及其之后的所有字符都被扫描过了,但是模式字符串中还有未被扫描的字符,则本次匹配失败,且之后也肯定匹配失败(长度不一样),因此返回 -1。

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
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
// 字符串匹配(暴力算法)。
int strStr(string haystack, string needle)
{
// 如果模式字符串为空,则返回 0。
if (needle.empty())
return 0;

// 两层循环。外层循环控制文本串,内层循环控制模式字符串。
for (string::size_type idx = 0; idx != haystack.size(); idx++)
{
// 定义两个下标,tempIdx 表示一次匹配过程中扫描文本串某个字符所在的下标,idxInner 表示一次匹配过程中扫描模式字符串某个字符所在的下标。
string::size_type tempIdx, idxInner;

for (idxInner = 0, tempIdx = idx; idxInner != needle.size() && tempIdx != haystack.size(); idxInner++, tempIdx++)
{
// 如果在扫描的过程中,出现某两个字符不相同的情况,则从文本串的下一个字符开始,进行下一次匹配。
if (needle[idxInner] != haystack[tempIdx])
break;
}

// 如果一次匹配过程中,模式字符串中的所有字符都被扫描过了,则匹配成功,返回这个位置所对应的下标。
if(idxInner == needle.size())
return idx;
// 如果在一次匹配过程中,文本串都被扫描过了,但是模式串中还有字符未被扫描,则返回 -1。
if (tempIdx == haystack.size())
return -1;
}

// 文本串扫描到最后也未能与模式字符串成功匹配,则返回 -1。
return -1;
}
};

int main(int argc, char const *argv[])
{
Solution s;

cout << s.strStr("mississippi", "issip") << endl;

return 0;
}

2 KMP 算法

2.1 KMP 算法的由来

考虑下面的字符串匹配: 28-1.png-48.6kB

对于暴力算法,在某一次匹配过程中,当 needle[6] 与 haystack[10] 失配时,在下一次匹配开始前,需要回溯文本串到本次匹配过程开始字符的下一个字符,作为下一次匹配过程匹配的首字符,这里就是 haystack[5],将模式字符串回溯至首字符,即 needle[0]。这样是很不效率的。

KMP算法的目的就是,在某一次匹配过程中,文本串和模式字符串的某个字符失配时,不需要回溯文本串,而是保持这个匹配位置不动。对于模式字符串,也不用总是回溯至模式字符串首位置,而是根据适当的情况,回溯至模式字符串前面的某个字符。也就是相当于将模式串向后移动一定的字符数。

那么应该将模式字符串回溯至哪个字符呢,或者说应当将模式串向后移动多少个字符呢?对于上图,观察到,对于模式字符串中失配字符 D 前的字符串 needle[0...5],它肯定和文本串中失配处的前面同样长度的字符串 haystack[4...9] 相同,因此,needle[4...5] 和 needle[8...9] 相同。而 needle[0...5] 中,有相同的前后缀 AB,即 needle[0...1] 与 needle[4...5]。所以,needle[0...1] 与 haystack[8...9] 相同。因此,只需要将模式字符串向右移动,直至 needle[0] 与 haystack[8] 对齐为止,移动步数为 4。然后就可以继续从 needle2 与 haystack[10] 进行匹配。如下图所示: 28-2.png-43.4kB

2.2 如何计算移动字符数?

当模式字符串中的某个字符与文本串中的某个字符失配时,如何计算模式串向右移动的步数?或者是如何确定模式串中的字符,使得在马上进行新的一次匹配过程中,该字符与本次匹配过程中失配时文本串中的这个字符继续进行匹配?

这要先引入字符串的前缀和后缀,以及最长相同前后缀的长度的概念。

对于字符串 ABCD,它的所有前缀为 A, AB, ABC;它的所有后缀为 D, CD, BCD。没有相同的前后缀,故而最长相同前后缀的长度为 0。 > 注意:一个字符串的前缀与后缀均不包括自身。

对于字符串 ABABA,它的所有前缀为 A, AB, ABA, ABAB;它的所有后缀为 A, BA, ABA, BABA。有两个相同的前后缀,分别为 A, ABA,故而最长相同前后缀的长度为 3。

回到上面的例子,needle[0...5],即 ABCDAB 的最长前后缀为 AB,故而它的最长前后缀长度为 2。当 needle[6] 与 haystack[10] 失配时,模式字符串所要向右移动的步数为 6 - 2 = 4(6 指的是失配字符的下标,2 指的是模式字符串失配字符前的字符构成的字符串的最长相同前后缀的长度)。也就是说,当 needle[6] 这个字符失配时,进行下一次匹配的时候,将 needle2 与 haystack[10] 继续进行匹配即可(2 指的就是上面提到的这个最长相同前后缀的长度)。形象地,可以将这种关系表示为 next[6] = 2。模式字符串中的每个字符的 next 值只与模式字符串本身有关,与文本串无关。

规定,模式字符串中的首字符对应的 next 值为 -1。将模式字符串中的所有字符对应的 next 值算出来,就组成了一个 next 数组。比如:ABCDABD 对应的 next 数组为 [-1, 0, 0, 0, 0, 1, 2]。

由以上可知,当模式字符串中某个字符在某一次匹配过程中失配时,则可以通过求出这个字符之前的所有字符构成的字符串的最长相同前后缀长度,来求出这个字符的 next 值。也就是说求模式字符串中某个字符的 next 值,是在该字符失配的假设下进行的,此时它前面的所有字符都与文本串中的某几个连续字符成功匹配。

2.3 如何实现计算移动步数的算法

上面提到,通过计算每个字符前的所有字符构成的字符串的最长相同前后缀长度,来得到这个字符的 next 值。这种方法实现起来效率太低,每次计算都要考虑前边的所有字符。事实上,可以通过一种较为高效的递推方法来实现,每次计算时,无需考虑到前面的所有字符。

假设要求 next[j + 1],那么首先考虑 next[j],令 next[j] = k。若 k = -1,或者 needle[k] 与 needle[j] 相同,则 next[j + 1] = k + 1。否则,令 j = k,再进行上面的判定。 > 注意:在每次比较两个字符是否相同时,总是针对前面的某个字符与 needle[j]。

比如:对于 needle = BBAB。它的每个字符的 next 值求解的具体过程为: 1. 初始时,next[0] = -1。

  1. 求 next1。首先获取 next[0] 的值,为 -1,所以 next1 = 0。

  2. 求 next2。首先获取 next1 的值,为 0,然后比较 needle[0] 与 needle1 是否相同。发现两者相同,故而 next2 = 0 + 1 = 1。

  3. 求 next3。首先获取 next2 的值,为 1,然后比较 needle1 与 needle2 是否相同。发现两者不同,然后获取 next1 的值,为 0,然后比较 needle[0] 与 needle2 是否相同。发现两者不同,然后获取 next[0] 的值,为 -1,所以 next3 = 0。

2.4 证明分析

上面求 next[j + 1] 时,令 next[j] = k,若 needle[k] 与 needle[j] 相同时,为什么 needle[0...(k - 1)] 与 needle[(j - k)...(j - 1)] 就一定相同?

反证法:

如果两者不同,那么 needle[0...(j - 1)] 的最长相同前后缀的长度必然不为 k,也就得不到 next[j] = k,矛盾。

比如说:ABCDABC,除了最后一个字符 C 外,其他所有字符的 next 值分别为 [-1, 0, 0, 0, 0, 1]。现在要求 next[6],即最后一个字符 C 的 next 值。首先 next[5] 为 1,因而比较 needle1 与 needle[5] 是否相同。发现相同,都为 B。同时还发现它们各自前面的相同长度的字符串也相同,这里就是 needle[0] 与 needle4,都为 A。假设两者不同,那么 needle[0...4] 的最长相同前后缀长度必比 1 小(因为相同的时候,最长相同前后缀长度为 1,即为 A,没有更长的相同前后缀了,故而,不同的时候,最长相同前后缀长度肯定比 1 小)。

2.5 如何利用求得的 next 数组进行匹配?

在一次匹配过程,若文本串中的 haystack[i] 与 needle[j] 正在进行匹配。如果两者相同,则匹配 haystack[i + 1] 与 needle[j + 1];如果两者不同,则查看 next[j],令 next[j] = k,继续匹配 haystack[i] 与 needle[k]。如果 k 为 -1,则对 haystack[i + 1] 与 needle[0] 进行匹配。具体匹配过程详见代码。

2.6 代码实现

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>
#include <string>

using namespace std;
class Solution
{
private:
// 存储模式字符串中所有字符的 next 的值。
vector<int> next;

// 递归函数。target 为每次需要进行比较的字符,也即需要求出 next 值的字符的前一个字符。indexofNext 为查询 next 数组时某个值对应的下标,初始时为需要求出 next 值的字符的前一个字符的下标。
int help(const string &needle, char target, int indexofNext)
{
// 取出 next 数组中下标为 indexofNext 的 next 值。
int tempIndexofNext = next[indexofNext];

// 如果它为 -1,则 next 值为 0。如果两者相同,则 next 值为它加上 1。
if (tempIndexofNext == -1 || needle[tempIndexofNext] == target)
return tempIndexofNext + 1;

// 否则,递归求 next 值。
return help(needle, target, tempIndexofNext);
}

// 构造模式字符串的 next 数组(递归方法)。
void createNext(const string &needle)
{
// 规定,如果模式字符串非空,则首字符的 next 值为 -1。并加入到 next 数组中。
next.push_back(-1);

// 依次生成后面每个字符的 next 值,并加入到 next 数组中。
for (int i = 1; i < needle.size(); i++)
next.push_back(help(needle, needle[i - 1], i - 1));
}

/*
// 构造模式字符串的 next 数组(非递归方法)。
void createNext(const string &needle)
{
// 规定,如果模式字符串非空,则首字符的 next 值为 -1。并加入到 next 数组中。
next.push_back(-1);

// 计算后面所有字符的 next 值。
for (int i = 1; i < needle.size(); i++)
{
// indexofNext 为查询 next 数组时某个值对应的下标,初始时为需要求出 next 值的字符的前一个字符的下标。
int indexofNext = i - 1;

// 循环遍历 next 数组。
while (indexofNext >= 0)
{
// 取出 next 数组中下标为 indexofNext 的 next 值。
int tempIndexofNext = next[indexofNext];

// 如果它为 -1,则 next 值为 0。然后停止遍历 next 数组,接着求下一个字符的 next 值。 如果两者相同,则 next 值为它加上 1。然后停止遍历 next 数组,接着求下一个字符的 next 值。
if (tempIndexofNext == -1 || needle[tempIndexofNext] == needle[i - 1])
{
next.push_back(tempIndexofNext + 1);
break;
}

// 否则,循环遍历 next 数组。
indexofNext = tempIndexofNext;
}
}
}
*/

public:
// 字符串匹配(KMP算法)。
int strStr(string haystack, string needle)
{
// 如果模式字符串为空,则返回 0。
if(needle.empty())
return 0;

// 生成模式字符串的 next 数组。
createNext(needle);

// indexofHaystack 为 haystack 中正在匹配字符的下标。indexofNeedle 为 needle 中正在匹配字符的下标。
int indexofHaystack, indexofNeedle;
indexofHaystack = indexofNeedle = 0;

// 进行匹配。
while(indexofHaystack < haystack.size() && indexofNeedle < int(needle.size()))
{
// 如果 indexofNeedle 为 -1,则从 haystack 的下一个字符,以及 needle 的首字符开始进行匹配。
if(indexofNeedle == -1)
{
indexofHaystack++;
indexofNeedle = 0;
continue;
}

// 如果正在匹配的两个字符相同,则对 haystack 的下一个字符以及 needle 的下一个字符进行匹配。
if(haystack[indexofHaystack] == needle[indexofNeedle])
{
indexofHaystack++;
indexofNeedle++;
}
// 否则,根据模式字符串的 next 数组,查看下一次匹配过程中模式字符串的哪一个字符进行匹配。
else
indexofNeedle = next[indexofNeedle];
}

// 循环结束后,如果 needle 中的字符都被匹配过了,则匹配成功,返回该模式字符串在文本串中的首位置的下标。
if(indexofNeedle == needle.size())
return indexofHaystack - needle.size();

// 否则(模式字符串中还有未被匹配的字符),而文本串的所有字符都被匹配过,则文本串中不存在子串与模式串匹配,返回 -1。
return -1;
}
};

int main(int argc, char const *argv[])
{
Solution s;

cout << s.strStr("mississippi", "issip") << endl;

return 0;
}

3 KMP 算法中 next 数组的改进

3.1 为什么要对 next 数组进行改进?

一次匹配如下图所示: 28-3.png-110kB

模式字符串的 b 与文本串中的 c 失配。根据 b 的 next 值,对模式字符串中的 needle1 与文本串中的 c 进行下一次匹配。由于 needle1 仍为 b,因此,再次匹配失败。然后根据 needle1 的 next 值,进行下一次匹配。如下图所示: 28-4.png-93.6kB

显然,由于 needle3 和 needle1 是相同的,因此当 needle3 与 文本串中的 c 匹配失配时,如果根据 next 值再对相同的字符 needle1 与文本串中的 c 匹配,则是多此一举。因此,需要对 next 数组进行优化。

3.2 如何优化 next 数组?

假设计算 next[j + 1]。如果根据之前计算 next 值的方法得到 next[j] 为 k,则首先比较 needle[k] 与 needle[j] 是否相同,以及 k 是否为 -1。

如果相同或者 k 为 -1,则将 k 加 1,然后保存这个 k 值,以作为该字符的未优化的 next 值,用以计算下一个字符的 next 值。然后判定 needle[j + 1] 与 needle[k] 是否相同。如果不同,则得到的这个 next 值无需优化;否则需要进行优化,优化后的 next 值即为 next[k]。

如果不同且 k 不为 -1,则令 j = k,然后查找 k 在 next 数组中的值(不再是使用未优化的 next 值),然后继续进行上面的。 > 规定,优化的 next 数组中,next[0] 仍为 -1。

比如:一个模式字符串为 issip,已经求出了前面 3 个字符的 next 值,分别为[-1, 0, 0]。

在求 needle3(即为 i)的 next 值时,首先获取 needle2 的未优化的 next 值,为 0,然后由于 needle[0] 与 needle3 相同,因此需要优化(优化前将 needle3 的未优化值存储,用以求取下一个字符的 next 值),next3 = next[0]。

在求 needle4(即为 p)的 next 值时,首先获取 needle3 的未优化的 next 值为 0(而非取 next3),然后由于 needle3 与 needle[0] 相同,故而 needle4 的未优化值为 1。由于 needle1 与 needle4 不同,因而 needle4 的 next 值无需进行优化,它的最终 next 值为 1。具体过程详见代码。

再得到优化了的 next 数组后,匹配过程同之前一样,不作任何变化。

3.3 分析证明

在求模式串中一个字符的 next 值的时候,假设得到的未优化值为 k,且这个字符与 needle[k] 相同,则需要优化。而优化的目的在于,找到一个与所求 next 值字符不同的一个字符。那为何最后优化的值就是 next[k]?也就是说,为何 needle[next[k]] 就一定与这个字符不同吗?而非 next[next[k]],或者 next[next[next[k]]],或者更多的递归层次?

反证法:

如果这个字符与 needle[next[k]] 相同,那么由于这个字符与 needle[k] 相同,那么 needle[k] 与 needle[next[k]] 也相同。而在求 needle[k] 的 next 值时,它最后得到的优化的 next 值 next[k] 对应的字符 needle[next[k]] 一定不会与 needle[k] 相同(优化的目的)。因此矛盾。

3.4 代码实现

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
private:
// 存储模式字符串中所有字符的 next 的值。
vector<int> next;

// 构造模式字符串的优化的 next 数组(非递归方法,递归方法很难实现)。
void createNextImprove(const string &needle)
{
// 规定,如果模式字符串非空,则首字符的 next 值为 -1。并加入到 next 数组中。
next.push_back(-1);
// 存储所求 next 值的字符的前一个字符的非优化(如果它的 next 值需要优化)时的 next 值。
int originalNext = -1;
// 计算后面所有字符的 next 值。
for (int i = 1; i < needle.size(); i++)
{
// indexofNext 为查询 next 数组时某个值对应的下标,初始时为需要求出 next 值的字符的前一个字符的下标。
int indexofNext = i - 1;

// 循环遍历 next 数组。
while (indexofNext >= 0)
{
// tempIndexofNext 为某个字符的 next 值。
int tempIndexofNext;
// 如果正在查询所要求出 next 值的字符的前一个字符的 next 值时,则将上一次循环得到的关于这个字符的未优化(如果它的 next 值需要优化)的 next 值赋值给它。
if (indexofNext == i - 1)
tempIndexofNext = originalNext;

// 否则,取出 next 数组中下标为 indexofNext 的 next 值。
else
tempIndexofNext = next[indexofNext];

// 如果它为 -1,则未优化的 next 值为 0。然后停止遍历 next 数组,接着求下一个字符的 next 值。如果两者相同,则未优化的 next 值为它加上 1。
if (tempIndexofNext == -1 || needle[tempIndexofNext] == needle[i - 1])
{
// 求出未优化的 next 值后,将其保存到 originalNext 中,用于求下一个字符的 next 值。
originalNext = ++tempIndexofNext;

// 然后判断。如果未优化的 next 值对应下标在 needle 中的字符,与正在求 next 值的这个字符不同,则无需优化。
if (needle[tempIndexofNext] != needle[i])
next.push_back(tempIndexofNext);
// 否则,所求字符的优化的 next 值为它的未优化的 next 值对应字符的 next 值。
else
next.push_back(next[tempIndexofNext]);

// 得到这个字符的 next 值后,退出循环,继续求下一个字符的 next 值。
break;
}

// 否则,循环遍历 next 数组。
indexofNext = tempIndexofNext;
}
}
}

public:
// 字符串匹配(KMP算法)。
int strStr(string haystack, string needle)
{
// 如果模式字符串为空,则返回 0。
if(needle.empty())
return 0;

// 生成模式字符串的改进后的 next 数组。
createNextImprove(needle);

// indexofHaystack 为 haystack 中正在匹配字符的下标。indexofNeedle 为 needle 中正在匹配字符的下标。
int indexofHaystack, indexofNeedle;
indexofHaystack = indexofNeedle = 0;

// 进行匹配。
while (indexofHaystack < haystack.size() && indexofNeedle < int(needle.size()))
{
// 如果 indexofNeedle 为 -1,则从 haystack 的下一个字符,以及 needle 的首字符开始进行匹配。
if (indexofNeedle == -1)
{
indexofHaystack++;
indexofNeedle = 0;
continue;
}

// 如果正在匹配的两个字符相同,则对 haystack 的下一个字符以及 needle 的下一个字符进行匹配。
if (haystack[indexofHaystack] == needle[indexofNeedle])
{
indexofHaystack++;
indexofNeedle++;
}
// 否则,根据模式字符串的 next 数组,查看下一次匹配过程中模式字符串的哪一个字符进行匹配。
else
indexofNeedle = next[indexofNeedle];
}

// 循环结束后,如果 needle 中的字符都被匹配过了,则匹配成功,返回该模式字符串在文本串中的首位置的下标。
if (indexofNeedle == needle.size())
return indexofHaystack - needle.size();

// 否则(模式字符串中还有未被匹配的字符),而文本串的所有字符都被匹配过,则文本串中不存在子串与模式串匹配,返回 -1。
return -1;
}
};

int main(int argc, char const *argv[])
{
Solution s;

cout << s.strStr("mississippi", "issip") << endl;

return 0;
}

Reference