字符串匹配(二)

1 BM 算法

匹配过程参见引用文章。下面就 BM算法 提出原因以及最为核心的两大规则进行说明。

1.1 BM 算法的由来

对于以下文本串和模式字符串, 28-5.JPG-64.1kB

needle3 与 haystack3 失配,发现 needle1 与坏字符相同(坏字符的定义见下面),因此,可以将模式串向右移动,直至 needle1 与 haystack3 对齐。

对于一下文本串和模式字符串, 28-6.JPG-58.5kB

needle2 与 haystack2 失配,发现模式串中存在一个前缀,它与最长后缀同为 ab ,因此可以将模式串向右移动,使得该前缀与文本串中的 ab 对齐。

1.2 坏字符规则及其映射表的构造

坏字符的定义如下图所示: 28-7.png-37.7kB

称在匹配过程中,匹配失败时文本串中的字符为坏字符。这里 S 就是一个坏字符。

根据 BM算法 原论文,根据坏字符规则所得到的移动距离为,坏字符在模式串中最右所在位置与模式串最后一个字符的距离,减去模式串中匹配失败的字符与模式串最后一个字符的距离。如果坏字符在模式串中不存在,则规定它与模式串最后一个字符的距离为这个模式串的长度,就相当于是在模式串最左边虚拟了一个坏字符。事实上,就是模式串中匹配失败的字符的下标减去坏字符在模式串中最右所在位置的下标。这个差值可能是正值,也可能是负值,但是绝对不可能是 0(因为那样的话,正在进行匹配的模式串中的字符与文本串中对应的字符相同,这样会匹配成功)。

至于如何实现坏字符规则,则可以预先构造一个坏字符映射表。key 为坏字符,key 为其在模式串中最有所在位置与模式串最后一个字符的距离。然后在匹配的时候,首先查找匹配失败时的坏字符是否存在于这个映射表中。若存在,则直接取出来;否则,则规定这个值为模式串的最大长度。然后将这个值再去减去模式串中匹配失败的字符与模式串最后一个字符的距离即可。 > 很多代码中,对于模式串最后一个字符,若它在模式串的前面不存在,则它对应的 value 为模式串的长度。事实上存在模式串匹配失败字符右边且恰好是最后一个字符为坏字符的情况。所以说仍然需要计算最后一个字符(若它在模式串前面不存在)到最后一个字符的距离,也就是 0。然后将其他工作交给好后缀规则完成。

按道理说,这个差值不应该为负值,因为模式串不可能向左移动。而且初次接触 BM算法的读者很可能会觉得,在移动的过程中,应该是找模式串匹配失败字符前面最近的一个坏字符,然后将这个模式串向右移动,使得找到的这个坏字符与文本串中的坏字符对齐。见下图: 28-8.JPG-59.1kB

needle3 与 haystack3 失配,按道理说,应该是向右移动一个字符的距离,使得 needle2 与 haystack3 对齐,这样更有意义点。若按照坏字符规则所定义的那样,则差值为 (4 - 4) - (4 - 3) = -1。

但是,作者之所以没有这样定义移动距离,是有一定道理的。试分析产生负值的情况。事实上就是,在匹配过程中,碰到匹配失败时,坏字符在模式串中匹配失败字符的右边出现。也就是说,若产生负值,那么在本次匹配中,至少匹配成功了一个字符。那如何在产生负值时能够使得模式串向右移动呢?这就要用到好后缀规则了。

1.3 好后缀及其数组的构造

有了好后缀规则,则没必要去找模式串匹配失败字符前面最近的一个坏字符了,只需要按照坏字符规则所定义的移动距离去计算就行了。也不用担心差值为负值的情况了。

好后缀的定义如下图所示: 28-9.png-42kB

称在匹配过程中,匹配失败时模式字符串匹配失败字符后面的字符串及其它的后缀子串为好后缀。该图中,MPLE, PLE, LE, E 均为好后缀。

好后缀规则分为以下三种情况:

  • 模式串中存在子串与最长好后缀匹配 28-10.png-37.7kB

  • 模式串中没有子串匹配上最长好后缀,但存在一个前缀与尽可能长的好后缀匹配 28-11.png-36.3kB

  • 上述两种情况都不存在 28-12.png-26.6kB

1.4 在字符串匹配过程,如果某个字符匹配失败,如何决策?

当模式串中的某个字符匹配失败时,则需要根据坏字符规则映射表与好后缀规则数组进行判定,取两者的最大值。由于是将模式串向右移动,因此再实际的代码执行中,相当于是根据本次匹配最开始时文本串的下标的基础上进行修改。所以,需要先计算出本次匹配过程中已经正确匹配的字符数,然后将其加到文本串扫描的下标。也即先将文本串扫描的下标移动到本次匹配时最开始的地方,然后再根据坏字符规则映射表与好后缀规则数组得到的最大值对文本串扫描的下标进行进一步的修改。

1.5 代码实现

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution
{
private:
// 模式串中出现的坏字的符映射表。key 为坏字符,value 为其在模式串中的最有位置与模式串的最后一个字符之间的距离。若坏字符不存在于模式字符串中,则距离为这个模式串的长度。
unordered_map<char, int> bad;
// 存储模式串中某个字符匹配失败时,根据它后面的好后缀与模式串中是否存在好后缀子串或者与好后缀相同的前缀,而移动的距离。
vector<int> good;

// 生成 bad 这个映射表。
// bad[char] 表示模式串中最右的 char 这个字符离最后一个字符的距离。
void createBadCharacterTable(const string &needle)
{
int length = needle.size();

for(int i = 0; i < length; i++)
bad[needle[i]] = length - 1 - i;
}

// 生成 suffix 这个数组。这个数组用于生成 good 这个 数组。
// suffix[i] 表示模式串中以 needle[i] 结尾的子串,与以最后一个字符结尾的子串的最长相同子串的长度。
void createSuffixTable(const string &needle, vector<int> &suffix)
{
int length = needle.size();
// 两个模式串的最长相同子串当然就为这个模式串。
suffix[length - 1] = length;

for (int i = length - 2; i >= 0; i--)
{
int commonSuffixLength = 0;

// 比较这两个子串,计算出在相同的情况下的最大长度。
for (int j = i, k = length - 1; j >= 0; j--, k--)
{
if (needle[j] != needle[k])
break;

commonSuffixLength++;
}

suffix[i] = commonSuffixLength;
}
}

// 生成 good 这个数组。good[i] 表示当 needle[i] 失配时,模式字符串应该向右移动的距离。
// 下面的 3 个 for 循环,一定要按照这个顺序进行。因为,根据好后缀规则,应当首先查找模式串中是否存在某个子串,使得其与最长后缀相同(当然还有其他条件)。如果不存在,则再找模式串中是否存在与某个好后缀相同的前缀。如果不存在,则相应的 good 值即为模式串长度。
void createGoodSuffixTable(const string &needle)
{
int length = needle.size();
vector<int> suffix(length);
// 生成 suffix 数组。
createSuffixTable(needle, suffix);
good.resize(length);

// 首先将所有的元素置为模式串长度。
for (int i = 0; i < length; i++)
good[i] = length;

// 从最长的好后缀开始(相当于是从最大的 suffix[i] 开始,它等于 i + 1,也就相当于是从最大的 i 开始),找出与某个好后缀 needle[length - 1 - i, length - 1] 尽可能长的相同的前缀 needle[0...i]。然后将 length - 1 - i 赋值给 good[0...length - 1 - suffix[i]]。
for (int i = length - 1; i >= 0; i--)
{
if (suffix[i] == i + 1)
{
for (int j = 0; j <= length - 1 - suffix[i]; j++)
{
if (good[j] == length)
good[j] = length - 1 - i;
}
}
}

// 然后找出模式串中与最长好后缀相同的且尽可能靠右的子串,使得这个子串的左边的字符不能与最长好后缀的左边的字符相同。然后将 length - 1 - i 赋给最长好后缀的左边的字符对应下标的 good。只能是扫描到 needle[length - 2],不能扫描最后一个字符,因为最后一个字符对应的 suffix 始终为 length,会导致下面这个 good 越界。
for(int i = 0; i <= length - 2; i++)
good[length - 1 - suffix[i]] = length - 1 - i;
}

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

// 分别生成 bad 映射表 以及 good 数组。
createBadCharacterTable(needle);
createGoodSuffixTable(needle);

// indexofhaystack 为扫描 haystack 的下标,indexofneedle 为扫描 needle 的下标。
int indexofhaystack, indexofneedle;
indexofhaystack = indexofneedle = needle.size() - 1;

// 进行比较。
while (indexofhaystack < haystack.size() && indexofneedle >= 0)
{
// 如果两者相同,则扫描各自的前一个字符。
if (haystack[indexofhaystack] == needle[indexofneedle])
{
indexofhaystack--;
indexofneedle--;
}
// 否则,找出下次匹配位置,继续进行匹配。
else
{
// 首先根据本次匹配失败中文本串中的坏字符到 bad 映射表中取出它与模式串中最后一个字符的距离。如果不存在,则这个距离就为 -1(相当于是在模式串的最左边虚拟出一个坏字符)。
int temp;
if (bad.find(haystack[indexofhaystack]) == bad.end())
temp = needle.size();
else
temp = bad[haystack[indexofhaystack]];

// 然后计算出本次匹配过程中已经正确匹配的字符数。
int delta = needle.size() - 1 - indexofneedle;

// 然后修改下一次匹配开始时文本串和模式字符串的下标。
// 根据坏字符规则,移动的距离是坏字符与模式串最后一个字符的距离,减去匹配失败的字符与最后一个字符的距离。根据好后缀规则,直接取出匹配失败的字符对应下标的 good 值。最后取最大者。
// 由于是移动整个模式串,且每次匹配都是从模式串的最后一个字符开始,因此相当于是将本次匹配最开始时文本串的下标向右移动。所以,需要先将 delta 加到 indexofhaystack。
indexofhaystack += delta + max(good[indexofneedle], int(temp - (needle.size() - 1 - indexofneedle)));
indexofneedle = needle.size() - 1;
}
}

// 如果是因为 indexofNeedle < 0 而循环结束,则表示匹配成功,返回模式串在文本串中的起始下标。
if (indexofneedle < 0)
return indexofhaystack + 1;

// 否则,indexofHaystack < 0,表示文本串中不存在子串和模式串匹配。
return -1;
}
};

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

cout << s.strStr("abacdab", "acdab") << endl;

return 0;
}

2 Horspool 算法

2.1 Horspool 算法的由来

28-13.png-15.1kB
28-13.png-15.1kB

如上图所示,当某一次匹配过程中匹配时,到模式串中查找尽可能右的且与文本串本次匹配窗口中的最后一个字符(这里也就是 haystack4)相同的字符(这里是 needle[0],而不是 needle4,否则移动距离为 0,这显然是不应该的)。然后将模式串向右移动,使得 needle[0] 与 haystack4 对齐,准备进行下一次的匹配。

2.2 构造映射表

根据上面的说明,要实现 Horspool算法,关键的就是要构造一个文本串中本次匹配窗口中的最后一个字符,与其在模式串中尽可能右位置到最后一个字符的距离的映射。

这类似于 BM算法中的坏字符规则映射表。但有一点不同的就是,这里是 尽可能靠右,而在 BM算法中是 最靠右。而且,对于 Horspool算法,由于所关注的字符始终是文本串本次匹配窗口中的最后一个字符(它对应与模式串的下标是固定的,总是 needle.size() - 1),而不像 BM算法中关注的是匹配失败时的坏字符(他对应于模式串的下标不固定),因此每次模式串向右移动的距离,就是当匹配失败时,根据文本串本次匹配窗口最后一个字符在映射表中对应值。

原因在于,在构造 BM算法的坏字符映射表时,若模式串中最后一个字符是坏字符,那么不管它是否在模式串的前面出现过,它的 bad 值为 0(相当于是最后一个字符的 good 值与其他字符的 good 值有相同的求法)。而在 Horspool算法中,由于始终是针对文本串中本次匹配窗口中的最后一个字符,到模式串中查找相同且尽可能靠右的字符,因此模式串中的最后一个字符与所要找的字符相同,且在模式串前面的字符中也存在同样的字符,则最后应该找的字符为模式串前面与所要找的字符相同的字符中最右的一个。若只有模式串的最后一个字符与所要找的字符相同,在它之前不存在其他字符与所要找到的字符相同,则规定所要找的字符与模式串最后一个字符的距离为模式串的长度(若为 0,则模式串不会发生移动,显然没意义)。

2.3 代码实现

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

using namespace std;

class Solution
{
private:
// 存储映射表。
unordered_map<char, int> table;

// 创建映射表。注意循环条件,不包含最后一个字符。
void createTable(const string &needle)
{
int length = needle.size();

for(int i = 0; i < length - 1; i++)
table[needle[i]] = length - 1 - i;
}

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

// 创建映射表。
createTable(needle);
int length = needle.size();
// 定义文本串和模式串的扫描下标。
int indexofhaystack, indexofneedle;
indexofhaystack = indexofneedle = needle.size() - 1;

// 开始匹配。
while(indexofhaystack < haystack.size() && indexofneedle >= 0)
{
// 如果文本串和模式串中当前扫描字符相同,则继续扫描各自前面的字符。
if (haystack[indexofhaystack] == needle[indexofneedle])
{
indexofhaystack--;
indexofneedle--;
}
// 否则,找出下次匹配位置,继续进行匹配。
else
{
// delta 为本次匹配过程中已经匹配成功的字符数。
int delta = needle.size() - 1 - indexofneedle;

// 然后修正 indexofhaystack 为文本串本次扫描窗口最后一个字符的下标。
indexofhaystack += delta;

// distance 为移动距离。
int distance;
// 如果文本串本次扫描窗口最后一个字符不在映射表中,则移动距离为模式串长度。
if (table.find(haystack[indexofhaystack]) == table.end())
distance = needle.size();
// 否则,取出它在映射表中对应的值,即为移动距离。
else
distance = table[haystack[indexofhaystack]];

// 然后改变文本串和模式串的下标,准备进行下一次匹配。
indexofhaystack += distance;
indexofneedle = needle.size() - 1;
}
}

// 如果是因为 indexofNeedle < 0 而循环结束,则表示匹配成功,返回模式串在原字符串中的起始下标。
if (indexofneedle < 0)
return indexofhaystack + 1;

// 否则,indexofHaystack < 0,表示原字符串中不存在子串和模式串匹配。
return -1;
}
};

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

cout << s.strStr("abacdab", "acdab") << endl;

return 0;
}

3 Sunday 算法

3.1 Sunday 算法的由来

28-14.png-14.6kB
28-14.png-14.6kB

Sunday算法与 Horspool算法不同的地方在于,它关注的是文本串中本次匹配窗口后面的那个字符,而非本次匹配窗口中的最后一个字符。

对于上图来说,在本次匹配失败时,它关注的是 haystack5,然后到模式串找到最靠右的相同的字符。发现不存在,因此将模式串中向右移动模式串长度加 1 的字符数(因为是关注的匹配窗口后边的那个字符,因此需要加 1)。

3.2 构造映射表

由于关注的字符不一样,因此构造的映射表也不一样。它的映射表的构造与 Horspool算法映射表的构造的不同之处在于,若模式串最后的一个字符与所要找到的字符相同,不管模式串前面是否存在这个字符,它在映射表中的值为 0。还有一点不同的地方在于,再求得距离值后,还要加上 1,才是最终相应字符在映射表中的值。

3.3 代码实现

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

using namespace std;

class Solution
{
private:
// 存储映射表。
unordered_map<char, int> table;

// 创建映射表。注意模式串中每个字符的值为它与最后一个字符的距离加 1。
void createTable(const string &needle)
{
int length = needle.size();

for (int i = 0; i < length; i++)
// length - 1 - i + 1 = length - i。
table[needle[i]] = length - i;
}

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

// 创建映射表。
createTable(needle);
int length = needle.size();
// 定义文本串和模式串的扫描下标。
int indexofhaystack, indexofneedle;
indexofhaystack = indexofneedle = needle.size() - 1;

// 开始匹配。
while (indexofhaystack < haystack.size() && indexofneedle >= 0)
{
// 如果文本串和模式串中当前扫描字符相同,则继续扫描各自前面的字符。
if (haystack[indexofhaystack] == needle[indexofneedle])
{
indexofhaystack--;
indexofneedle--;
}
// 否则,找出下次匹配位置,继续进行匹配。
else
{
// delta 为本次匹配过程中已经匹配成功的字符数。
int delta = needle.size() - 1 - indexofneedle;

// 然后修正 indexofhaystack 为文本串本次扫描窗口最后一个字符的下标。
indexofhaystack += delta;

// 如果本次匹配失败,且 haystack[indexofhaystack] 为文本串中的最后一个字符,则返回 -1。
if (indexofhaystack + 1 >= haystack.size())
return -1;

// distance 为移动距离。
int distance;
// 如果文本串本次扫描窗口后面的那个字符不在映射表中,则移动距离为模式串长度加 1。
if (table.find(haystack[indexofhaystack + 1]) == table.end())
distance = needle.size() + 1;
// 否则,取出它在映射表中对应的值,即为移动距离。
else
distance = table[haystack[indexofhaystack + 1]];

// 然后改变文本串和模式串的下标,准备进行下一次匹配。
indexofhaystack += distance;
indexofneedle = needle.size() - 1;
}
}

// 如果是因为 indexofNeedle < 0 而循环结束,则表示匹配成功,返回模式串在原字符串中的起始下标。
if (indexofneedle < 0)
return indexofhaystack + 1;

// 否则,indexofHaystack < 0,表示原字符串中不存在子串和模式串匹配。
return -1;
}
};

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

cout << s.strStr("abacdab", "acdab") << endl;

return 0;
}

Reference