字符串精确匹配

  |  

摘要: 字符串精确匹配方法汇总

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们以 leetcode 第 28 题为模板题,总结一下字符串精确匹配的各种算法。

  • 字符串精确匹配主流算法
    • 暴力算法(双串单向双指针),也叫 BF 算法
    • 字符串哈希, 也叫 RK 算法
    • MP 和 KMP 算法(有的地方也叫 KMP 和 扩展 KMP 算法)
    • BM 算法
    • Sunday 算法
    • horspool 算法
  • 以 MP 算法的 mpnext 数组为组件的题目
  • gcc 的 strstr; STL 的 std::string::find 和 std::search
  • STL 中与匹配相关的算法
  • 字符串算法专著 《Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology》 作者 Dan Gusfield

$1 题目

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。

示例 1:
输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:”sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:
输入:haystack = “leetcode”, needle = “leeto”
输出:-1
解释:”leeto” 没有在 “leetcode” 中出现,所以返回 -1 。

提示:

1
2
1 <= haystack.length, needle.length <= 1e4
haystack 和 needle 仅由小写英文字符组成

$2 题解

字符串精确匹配是指在目标文本串 s(s[0..n-1]),中检索子串 p(p[0..m-1]) 的过程。

s 称为主串,长度为 n,p 称为模式串,长度为 m。

算法1: 暴力(双指针)

暴力算法也称 BF(Brute Force) 算法,核心思想是枚举主串的各个字符,作为子串的起点,然后比较各个子串与模式串是否相等。s 一共有 n - m + 1 个子串, 需要枚举 n - m + 1 个起点(0, 1, …, n - m)。

对于每个枚举到的子串,与模式串 p 进行逐字符比较,子串的比较时间复杂度 $O(m)$,总时间复杂度 $O(m(n-m))$。

BF 算法的低效主要是由于某个子串匹配失败时,s[i] != p[j],需要将 i, j 都回溯。没有利用 p[0..j-1] 部分匹配的结果。

代码(C++)

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
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
if(haystack.empty()) return -1;
int n = haystack.size(), m = needle.size();
if(n < m) return -1;
int left = 0;
while(left <= n - m)
{
if(haystack[left] == needle[0])
{
int right = left + 1;
while(right - left < m)
{
if(haystack[right] == needle[right - left]) ++right;
else break;
}
if(right - left == m) return left;
}
++left;
}
return -1;
}
};

算法2: 字符串哈希

通过字符串哈希解决字符串精确匹配问题的原理与实现,参考文章 字符串哈希

算法3: MP 与 KMP

算法4: BM 算法

Boyer-Moore 算法,1977 年提出。

p 从左向右移动,固定 p 之后字符的比较从右向左。当出现失配时,用两个规则共同得出 p 向右偏移的量。两个规则分别是坏字符偏移,好后缀偏移。

假设目前 p 已经固定,正在对比 s[i..i+m-1] 和 p[0..m-1]。对比到 s[i+j] 和 p[j] 出现失配 s[i+j] != p[j]

此时有 s[i+j+1..i+m-1] = p[j+1..m-1]。 记 a = p[j], b = s[i+j], u = p[j+1..m-1],u 称为好后缀,b 称为坏字符

下面分析当前情况下的好后缀偏移和坏字符偏移。

1. 好后缀偏移

  • 情况1: 在 p 中 u 再次出现,记为 u’,且 u’ 左侧是一个不同于 a 的字符 c 时,则将从右往左出现的第一个 u’ 与 s[i+j+1..i+m-1] 对齐,实现该对齐需要的偏移量存储在预处理数组 bmgs[j]。

  • 情况2: 在 p 中 u 没有再次出现,或者再次出现的 u 左侧都是 a,那么将 s[i+j+1..i+m-1] 中的最长后缀 v 与 p 中的 v 对齐,实现该对齐需要的偏移量也存储在预处理数组 bmgs[j]。

为了实现好后缀规则,需要定义一个数组suffix,其中suffix[j] = s 表示以 j 为右边界,与模式串后缀匹配的最大长度。即满足 p[j-s..j] == P[m-1-s..m-1] 的最大长度 s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void get_suff(const string& p, vector<int>& suffix)
{
int m = p.size();
suffix[m - 1] = m;
int k;
for(int j = m - 2; j >= 0; --j)
{
k = j;
// k = j - s;
while(k >= 0 && p[k] == p[m - 1 - j + k])
--k;
suffix[j] = j - k;
}
}

若一个字符同时符合上述两种情况,那么我们选取最小的bmGs[j]。

比如当模式传中既有子串可以匹配上好后串,又有前缀可以匹配好后串的后串,那么此时我们应该按照前者来移动模式串,也就是bmGs[j]较小的那种情况。故而每次修改bmGs[j]都应该使其变小。

因此代码中 1,2,3 的顺序是必要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> get_bmgs(const string& p)
{
int m = p.size();
vector<int> bmgs(m, 0);
vector<int> suffix(m, 0);
get_suff(p, suffix); // suffix[j] := 以 j 为结尾的子串匹配好后缀的最长匹配长度
// 1. 没有好后缀 没有公共前缀
for(int j = 0; j < m; ++j)
bmgs[j] = m;
// 2. 没有好后缀 有公共前缀 调用 suffix 但是要右移一位 类似KMP里的next数组
int j = 0;
for(int i = m - 1; i >= 0; --i)
if(suffix[i] == i + 1)
for(; j < m - 1 - i; ++j)
if(bmgs[j] == m) //保证每个位置不会重复修改
bmgs[j] = m - 1 - i;
// 3. 有好后缀 有公共前缀
for(int i = 0; i < m - 1; ++i)
bmgs[m - 1 - suffix[i]] = m - 1 - i; //移动距离
return bmgs;
}

2. 坏字符偏移

  • 情况1: 在 p[0..m-2] 中,将从右到左 b 首次出现的位置与 s[i+j] 对齐,实现该对齐需要的偏移量存储在预处理数组 bmbc[b] 中。

  • 情况2: 在 p 中没有 b,则将 p[0] 与 s[i+j+1] 对齐,实现该对齐的偏移量也存储在预处理数组 bmbc[b] 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
void get_bmbc(const string& s, const string& p, unordered_map<char, int>& bmbc)
{
int m = p.size();
for(const char& ch: s)
if(bmbc.find(ch) == bmbc.end())
bmbc[ch] = m;
for(int j = 1; j < m; ++j)
{
if(bmbc[p[m - 1 - j]] != m)
continue;
bmbc[p[m - 1 - j]] = j;
}
}

预处理好 bmbc 和 bmgs 之后就可以开始匹配过程了。

出现失配 s[i+j] != p[j] 后,p 向右的偏移量是 max(bmgs[i], bmbc[b] - m + i + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int bm_match(const string& s, const string& p, unordered_map<char, int>& bmbc, const vector<int>& bmgs)
{
int n = s.size(), m = p.size();
int i = 0;
while (i <= n - m)
{
int j = m - 1;
while(j >= 0 && p[j] == s[i + j])
--j;
if(j < 0)
{
return i;
// i += bmgs[0]; // 找到完整匹配后仍继续往后找下一个完整匹配
}
else
i += max(bmgs[j], bmbc[s[i + j]] - m + 1 + j);
}
return -1;
}

根据以上讨论,可以将 bmgs 和 bmbc 写出完整定义:

bmbc 表的容量是 s 中元素种类数。

  • 条件1:对于每个 $j < k < m,s \geq k 或者 p[k-s] = p[k]$。
  • 条件2:$若 s < j,则 p[j - s] \neq p[j]$。

条件1用于计算p的某个后缀出去自身外的从最优侧开始出现出现时对应的偏移量(包含了前面讨论的两种情况);条件2确保计算到 p 的第 j 个位置。

例子:

以 p = GCAGAGAG 为例, s = “GCATCGCAGAGAGTATACAGTACG”, s 中的元素集合为 A, G, T, C

j 0 1 2 3 4 5 6 7
p[j] G C A G A G A G
bmgs[j] 7 7 7 2 7 4 7 1
b A C G T
bmbc[b] 1 6 2 8

代码(C++)

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
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
unordered_map<char, int> bmbc;
get_bmbc(haystack, needle, bmbc);
vector<int> bmgs = get_bmgs(needle);
return bm_match(haystack, needle, bmbc, bmgs);
}

int bm_match(const string& s, const string& p, unordered_map<char, int>& bmbc, const vector<int>& bmgs)
{
int n = s.size(), m = p.size();
int i = 0;
while (i <= n - m)
{
int j = m - 1;
while(j >= 0 && p[j] == s[i + j])
--j;
if(j < 0)
{
return i;
// i += bmgs[0]; // 找到完整匹配后仍继续往后找下一个完整匹配
}
else
i += max(bmgs[j], bmbc[s[i + j]] - m + 1 + j);
}
return -1;
}

void get_bmbc(const string& s, const string& p, unordered_map<char, int>& bmbc)
{
int m = p.size();
for(const char& ch: s)
if(bmbc.find(ch) == bmbc.end())
bmbc[ch] = m;
for(int j = 1; j < m; ++j)
{
if(bmbc[p[m - 1 - j]] != m)
continue;
bmbc[p[m - 1 - j]] = j;
}
}

vector<int> get_bmgs(const string& p)
{
// 若一个字符同时符合上述两种情况,那么我们选取最小的bmGs[j]。
// 比如当模式传中既有子串可以匹配上好后串,又有前缀可以匹配好后串的后串,
// 那么此时我们应该按照前者来移动模式串,也就是bmGs[j]较小的那种情况。
// 故而每次修改bmGs[j]都应该使其变小
// 因此代码中 1,2,3 的顺序是必要的
int m = p.size();
vector<int> bmgs(m, 0);
vector<int> suffix(m, 0);
get_suff(p, suffix); // suffix[j] := 以 j 为结尾的子串匹配好后缀的最长匹配长度
// 1. 没有好后缀 没有公共前缀
for(int j = 0; j < m; ++j)
bmgs[j] = m;
// 2. 没有好后缀 有公共前缀 调用 suffix 但是要右移一位 类似KMP里的next数组
int j = 0;
for(int i = m - 1; i >= 0; --i)
if(suffix[i] == i + 1)
for(; j < m - 1 - i; ++j)
if(bmgs[j] == m) //保证每个位置不会重复修改
bmgs[j] = m - 1 - i;
// 3. 有好后缀 有公共前缀
for(int i = 0; i < m - 1; ++i)
bmgs[m - 1 - suffix[i]] = m - 1 - i; //移动距离
return bmgs;
}

void get_suff(const string& p, vector<int>& suffix)
{
// 为了实现好后缀规则,需要定义一个数组suffix,其中suffix[j] = s 表示以 j 为右边界,
// 与模式串后缀匹配的最大长度,
// 即满足p[j-s..j] == P[m-1-s..m-1] 的最大长度 s。
int m = p.size();
suffix[m - 1] = m;
int k;
for(int j = m - 2; j >= 0; --j)
{
k = j;
// k = j - s;
while(k >= 0 && p[k] == p[m - 1 - j + k])
--k;
suffix[j] = j - k;
}
}
};

算法5: sunday 算法

Sunday 在 BM 的基础上做了一些改动。1990 年 Daniel M.Sunday 提出。

Sunday 是从前往后匹配(BM 是从后往前),关注主串 s 中参与匹配的最末字符的下一位,而不是正在匹配(参与比较)的字符。

Sunday 算法对于关注字符的策略的策略:

  1. 关注的字符没有在 p 中出现,则直接跳过。
  2. 关注的字符在 p 中出现过,则 移动位数 = 该字符在子串中最右边出现的位置到尾部的距离 + 1

例如 s = substring, p = search。i = 0 时,s[i + 1] != p[i],匹配失败,此时看关注字符决定转移步数:关注字符为 s[i + m] = i,该字符在 p 中没有出现,shift[i] = m + 1。而当 i = 7 时,s[i + 0] != p[0],匹配失败,此时关注字符为 s[i + m] = r,该字符在 p 的最右出现位置为 3,则 shift[i] = m - 3

缺点:与 BM 一样,移动取决于子串。当子串中重复比较多时效率变低。例如 s = TGGGGTGGGGTGGGG, p = GGGGG。

匹配机制过程:

目标字符串 s, 模式串 p。当前子串起点 i(初始为 0),待匹配字符串 s[i..i+m-1]。

若完整匹配,则返回 i,不匹配,则查看 s 的后一位字符 c = s[i+m]

若c存在于 p 中,则 i = i + 偏移表[c],否则,i = i + m + 1;

重复以上直到 i + m > n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int sunday_match(const string& s, const string& p, unordered_map<char, int>& shift)
{
int n = s.size(), m = p.size();
int i = 0;
while (i <= n - m)
{
int j = m - 1;
while(j >= 0 && p[j] == s[i + j])
--j;
if(j < 0)
return i;
else
{
if(i + m >= n)
return -1;
i += shift[s[i + m]];
}
}
return -1;
}

偏移表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void get_shift(const string& s, const string& p, unordered_map<char, int>& shift)
{
int m = p.size();
for(const char& ch: s)
if(shift.find(ch) == shift.end())
shift[ch] = m + 1;
for(const char& ch: p)
if(shift.find(ch) == shift.end())
shift[ch] = m + 1;
for(int j = 0; j < m; ++j)
{
if(shift[p[m - 1 - j]] != m + 1)
continue;
shift[p[m - 1 - j]] = j + 1;
}
}

代码(C++)

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
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
unordered_map<char, int> shift;
get_shift(haystack, needle, shift);
return sunday_match(haystack, needle, shift);
}

int sunday_match(const string& s, const string& p, unordered_map<char, int>& shift)
{
int n = s.size(), m = p.size();
int i = 0;
while (i <= n - m)
{
int j = m - 1;
while(j >= 0 && p[j] == s[i + j])
--j;
if(j < 0)
return i;
else
{
if(i + m >= n)
return -1;
i += shift[s[i + m]];
}
}
return -1;
}

void get_shift(const string& s, const string& p, unordered_map<char, int>& shift)
{
int m = p.size();
for(const char& ch: s)
if(shift.find(ch) == shift.end())
shift[ch] = m + 1;
for(const char& ch: p)
if(shift.find(ch) == shift.end())
shift[ch] = m + 1;
for(int j = 0; j < m; ++j)
{
if(shift[p[m - 1 - j]] != m + 1)
continue;
shift[p[m - 1 - j]] = j + 1;
}
}
};

算法6: horspool 算法

Horspool 算法是 BM 算法的一个简化版本,与 BM 一样,也是从右向左比较(Sunday 是从左到右)。

比较 s[i+0 .. i+m-1] ~ p[0..m-1],从 s[i+m-1] 与 p[m-1] 开始。直到匹配成功或者某处不相等。失配后,看主串 s 的匹配窗口中的最后一个字符 \beta = s[i+m-1 在模式串 p 中的下一个出现位置,将窗口向右移动。

  1. \beta 在 p 中未出现,shift[i] = m (第一次比较就失配 s[i+m-1]!=p[m-1])。
  2. \beta 在 p 中出现,且 p[i + m - 1] != \beta,则将 p 中最右边的 \betas[i] 对齐
  3. \beta 在 p 中出现,且 p[i + m - 1] == \beta,但其余元素中没有 \beta,与情况 1 一样 (第一次比较就失配 s[i+m-1]!=p[m-1])
  4. \beta 在 p 中出现,且 p[i + m - 1] == \beta,其余元素中也有 \beta,与情况 2 一样。

Horspool 算法与 BM 相比,改进了坏字符规则。

偏移表

unordered_map<char, int> 记录每一个字符在模式串中距离最右边的距离。

代码(C++)

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
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
int m = needle.size();
vector<int> shift(26, m);
get_shift(needle, shift);
vector<int> matches = horspool_match(haystack, needle, shift);
if(matches.empty())
return -1;
return matches.front();
}

private:
vector<int> horspool_match(const string& s, const string& p, const vector<int>& shift)
{
int m = p.size(), n = s.size();
int i = 0;
vector<int> result;
while(i <= n - m)
{
// s[i..i+m-1] 与 p[0..m-1]
bool match = false;
for(int j = m - 1; j >= 0; --j)
{
if(s[i + j] != p[j])
break;
if(j == 0)
match = true;
}
if(match)
result.push_back(i);
i += shift[s[i + m - 1] - 'a'];
}
return result;
}

void get_shift(const string& p, vector<int>& shift)
{
int m = p.size();
for(int i = 0; i < m - 1; ++i)
shift[p[i] - 'a'] = min(shift[p[i] - 'a'], m - i - 1);
}
};

$3 扩展1: 利用 mpnext 数组的题目

1
2
3
4
5
6
7
8
9
10
11
12
string shortestPalindrome(string s) {
if(s.empty()) return "";
int m = s.size();
string t = s + '#' + s;
reverse(t.begin() + m + 1, t.end());
vector<int> mpnext = get_mpnext(t);
int n_add = s.size() - mpnext.back();
string result = s.substr(m - n_add);
reverse(result.begin(), result.end());
result += s;
return result;
}
1
2
3
4
5
6
bool repeatedSubstringPattern(string s) 
{
int n = s.size();
vector<int> mpnext = get_mpnext(s);
return mpnext[n] && n % (n - mpnext[n]) == 0;
}
1
2
3
4
5
6
string longestPrefix(string s) {
int n = s.size();
vector<int> mpnext = get_mpnext(s);
int len = mpnext.back();
return s.substr(0, len);
}

$4 扩展2: STL 中与匹配相关的算法

  • std::find, std::find_if, std::find_if_not
  • std::search, std::search_n
  • std::regex_match, std::regex_search, std::regex_replace

$5 扩展3: STL 中的 string

gcc 中 strstr 的朴素实现

https://github.com/gcc-mirror/gcc/blob/41d6b10e96a1de98e90a7c0378437c3255814b16/libiberty/strstr.c

里面有句注释,如果系统有自带 strstr 的话,优先用系统的 strstr 而不是 gcc 的。

1
2
/* Simple implementation of strstr for systems without it.
This function is in the public domain. */

std::string::find函数和C的标准库中strstr函数实现类似,std::string::find 用的就是 BF 算法。在大多数常见场景下,需要匹配的字符是比较短的,BF 算法速度很快。在使用KMP算法的时候,反而还需要进行预处理。

现在 C++ 的高效字符串搜索有 std::search 泛型算法。用的是 BM 算法https://en.cppreference.com/w/cpp/algorithm/search。
此外BM算法常用于文本编辑器中的搜索匹配功能,比如GNU grep。

在检索的场景下,字符串算法是一个单独的大课题,有专著 《Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology》 作者 Dan Gusfield


Share