0%

字符串模式匹配算法(BF/KMP/BM/Sunday)

28.实现 strStr()(KMP算法/BM算法/Sunday算法)

标注

来源:力扣(LeetCode
链接:https://leetcode-cn.com/problemset/algorithms/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

题解

这题的两个参数很有意思:haystackneedle
出自 “Find a needle in a haystack.”,译为大海捞针

库函数indexOf()

1
2
3
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}

暴力匹配(brute-force search)

暴力匹配法,遍历主串,当主串索引字符与模式串相等时,就尝试匹配

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int strStr(String haystack, String needle) {
int len = haystack.length();
int targetLen = needle.length();
if (targetLen == 0) {
return 0;
}
for (int i = 0; i < len; i++) {
if (haystack.charAt(i) == needle.charAt(0)) {
int cnt = 1;
while (cnt < targetLen && i + cnt < len) {
if (haystack.charAt(i + cnt) == needle.charAt(cnt)) {
cnt++;
} else {
break;
}
}
if (cnt == targetLen) {
return i;
}
}
}
return -1;
}

算法分析:

  • 时间复杂度:O(n * m)
  • 空间复杂度:O(1)

KMP 算法

简介:KMP 算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称 KMP 算法)。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 函数实现,函数本身包含了模式串的局部匹配信息

大学课程数据结构(严蔚敏版)已经介绍过KMP算法,这里简单复习一下

首先是next[]数组的求解

我们假设有这样一个模式串:ababca,对于其next[]数组,简单概括一下,第一位0,第二位1,从第三位开始,看前几位首位是否匹配,next[i]为匹配的字符数+1,示例如下:

模式串 a b a b c a d
next[] 0 1 1 2 3 1 2

但这个next[]数组是建立在字符串是从索引1开始的,所以简单修改

模式串 a b a b c a d
next[] -1 0 0 1 2 0 1

附上next[]数组算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void get_next(String model, int len, int[] next) {
// i 是模式串的索引,只增不减
int i = 0;
// j 是 next[] 的索引
int j = -1;
// 首先给 next[0] 赋值
next[0] = -1;
while (i < len - 1) {
// 匹配的情况下递增索引 i and j,并给 next[i] 赋值
if (j == -1 || model.charAt(i) == model.charAt(j)) {
i++;
j++;
next[i] = j;
}
else { // 不匹配的话把 j 回溯到适当位置
j = next[j];
}
}
}

代码如下

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
public int strStr(String haystack, String needle) {
int len = haystack.length();
int targetLen = needle.length();
if (targetLen == 0) {
return 0;
}

int next[] = new int[targetLen];
get_next(needle, targetLen, next);

int i = 0;
int j = 0;
while (i < len && j < targetLen) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
else {
j = next[j];
}
}
if (j == targetLen) {
return i - targetLen;
}
else {
return -1;
}
}

public void get_next(String model, int len, int[] next) {
int i = 0;
int j = -1;
next[0] = -1;
while (i < len - 1) {
if (j == -1 || model.charAt(i) == model.charAt(j)) {
i++;
j++;
next[i] = j;
}
else {
j = next[j];
}
}
}

算法分析:

  • 时间复杂度:O(n+m)
  • 空间复杂度:O(m)

当然,KMP算法可以改进:当模式串中有多个连续重复的元素,next[]就可以优化

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
public void get_next(String model, int len, int[] next) {
// i 是模式串的索引,只增不减
int i = 0;
// j 是 next[] 的索引
int j = -1;
// 首先给 next[0] 赋值
next[0] = -1;
while (i < len - 1) {
// 匹配的情况下递增索引 i and j,并给 next[i] 赋值
if (j == -1 || model.charAt(i) == model.charAt(j)) {
i++;
j++;
//==================== 优化处 ======================//
// 如果当前字符与前缀字符不同,就和没优化前进行相同操作
if (model.charAt(i) != model.charAt(j)) {
next[i] = j;
} else { // 如果当前字符与前缀字符相同
next[i] = next[j];
}
//==================== 优化处 ======================//
}
else { // 不匹配的话回溯到适当位置
j = next[j];
}
}
}

BM 算法

简介:Boyer-Moore 字符串搜索算法是一种非常高效的字符串搜索算法。它由 Bob Boyer 和 J Strother Moore 设计于1977年。此算法仅对搜索目标字符串(关键字)进行预处理,而非被搜索的字符串。虽然 Boyer-Moore 算法的执行时间同样线性依赖于被搜索字符串的大小,但是通常仅为其它算法的一小部分:它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长,算法速度越快

现代许多文本处理器在搜索功能这一块都采用了主流的 BM 算法

在讲 BM 算法之前,我们用网上常用的例子模仿一下过程

文本串:”HERE IS A SIMPLE EXAMPLE”
模式串:”EXAMPLE”

索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
文本串 H E R E I S A S I M P L E E X A M P L E
模式串 E X A M P L E
第一次 E X A M P L E
第二次 E X A M P L E
第三次 E X A M P L E
第四次 E X A M P L E

首先,需要引入两个概念:坏字符规则和好后缀规则

1)坏字符规则(bad character rule)

概念:坏字符,就是模式串与文本串在从右向左的匹配过程中,文本串中出现的第一个不与模式串匹配的字符

举个例子:

索引 0 1 2 3 4 5 6 7
文本串 a b c a d b c d
模式串 a b d

如上表格所示,文本串的第 2 为字符c就叫做坏字符,不考虑好后缀的情况下,可以直接把模式串后移到文本串第 3 位,如下所示

索引 0 1 2 3 4 5 6 7
文本串 a b c a d b c d
模式串 a b d

但是,如果文本串与模式串是如下情况,可以发现,显然移动的距离过大了

索引 0 1 2 3 4 5 6 7
文本串 a b c d d b c d
模式串 b c d
移动后 b c d

其实只需移动到第 1 位即可,这时候就需要好后缀规则辅助

索引 0 1 2 3 4 5 6 7
文本串 a b c d d b c d
模式串 b c d

2)好后缀规则(good suffix shift)

概念:好后缀,就是模式串与文本串在从右向左的匹配过程中,文本串中与模式串匹配的部分

例如:

索引 0 1 2 3 4 5 6 7 8
文本串 a b c a d b c d e
模式串 a d c a d

匹配部分"ad"就叫做好后缀,我们好后缀"ad",在模式串中搜索是否有第二个匹配部分"ad"',如果有,便移动模式串中另一个匹配部分与文本串中的好后缀对其,如下

索引 0 1 2 3 4 5 6 7 8
文本串 a b c a d b c d e
模式串 a d c a d
移动后 a d c a d

算法实现

先实现生成坏字符数组的算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* ASCII 码表的长度
*/
private static int SIZE = 256;

/**
* 生成坏字符数组 bc[]
* @param bc 生成的坏字符数组
* @param pattern 模式串
* @param len 模式串的长度
*/
private void generateBC(String pattern, int len, int[] bc) {
for (int i = 0; i < SIZE; i++) {
bc[i] = -1;
}
for (int i = 0; i < len; i++) {
bc[pattern.charAt(i)] = i;
}
}
接着生成好后缀数组gs[]

实际上好后缀数组生成有三种情况:

  1. 好后缀在模式串中还有完全相同的部分
  2. 好后缀的后某一部分在模式串中还有完全相同的部分
  3. 好后缀在模式串中再无完全相同的部分

以模式串abcabc列个suffix[]

索引 0 1 2 3 4 5
模式串 a b c a b c
后缀子串 长度 suffix[]
c 1 suffix[1] = 2
bc 2 suffix[2] = 1
abc 3 suffix[3] = 0
cabc 4 suffix[4] = -1
bcabc 5 suffix[5] = -1

生成suffix[]数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 生成 suffix[] 数组
* @param pattern 模式串
* @param len 模式串长度
* @param suffix
*/
private void generateSuffix(String pattern, int len, int[] suffix) {
suffix[len - 1] = len;
for (int i = len - 2; i >= 0; i--) {
int index = i;
while (index >= 0 && pattern.charAt(index) == pattern.charAt(len - 1 + index - i)) {
index--;
}
suffix[i] = i - index;
}
}

生成好后缀数组gs[]

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
/**
* 生成好后缀数组 gs[]
* @param pattern 模式串
* @param len 模式串长度
* @param gs 好后缀数组
*/
private void generateGS(String pattern, int len, int[] gs) {
int[] suffix = new int[len];
generateSuffix(pattern, len, suffix);

// 第三种情况
for (int i = 0; i < len; i++) {
gs[i] = len;
}

// 第二种情况
/* 从右向左扫描,确保模式串移动距离最少 */
for (int i = len - 1; i >= 0; i--) {
if (suffix[i] == i + 1) {
for (int j = 0; j < len - 1 - i; j++) {
// 确保 gs[j] 只被修改一次
if (gs[j] == len) {
gs[j] = len - 1 - i;
}
}
}
}

// 第一种情况
for (int i = 0; i < len - 1; i++) {
gs[len - 1 - suffix[i]] = len - 1 - i;
}
}
完整代码

求得了坏字符数组和好后缀数组,接下来,每次不匹配时移动的距离就取两个中最大的一个即可

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
class Solution {
/**
* ASCII 码表的长度
*/
private static final int SIZE = 256;

/**
* 生成坏字符数组 bc[]
* @param bc 生成的坏字符数组
* @param pattern 模式串
* @param len 模式串的长度
*/
private void generateBC(String pattern, int len, int[] bc) {
for (int i = 0; i < SIZE; i++) {
bc[i] = -1;
}
for (int i = 0; i < len; i++) {
bc[pattern.charAt(i)] = i;
}
}

/**
* 生成 suffix[] 数组
* @param pattern 模式串
* @param len 模式串长度
* @param suffix
*/
private void generateSuffix(String pattern, int len, int[] suffix) {
suffix[len - 1] = len;
for (int i = len - 2; i >= 0; i--) {
int index = i;
while (index >= 0 && pattern.charAt(index) == pattern.charAt(len - 1 + index - i)) {
index--;
}
suffix[i] = i - index;
}
}

/**
* 生成好后缀数组 gs[]
* @param pattern 模式串
* @param len 模式串长度
* @param gs 好后缀数组
*/
private void generateGS(String pattern, int len, int[] gs) {
int[] suffix = new int[len];
generateSuffix(pattern, len, suffix);

// 第三种情况
for (int i = 0; i < len; i++) {
gs[i] = len;
}

// 第二种情况
/* 从右向左扫描,确保模式串移动距离最少 */
for (int i = len - 1; i >= 0; i--) {
if (suffix[i] == i + 1) {
for (int j = 0; j < len - 1 - i; j++) {
// 确保 gs[j] 只被修改一次
if (gs[j] == len) {
gs[j] = len - 1 - i;
}
}
}
}

// 第一种情况
for (int i = 0; i < len - 1; i++) {
gs[len - 1 - suffix[i]] = len - 1 - i;
}
}

public int strStr(String haystack, String needle) {
int len = haystack.length();
int ptnLen = needle.length();
if (ptnLen == 0) {
return 0;
}

int[] bc = new int[SIZE];
int[] gs = new int[ptnLen];
generateBC(needle, ptnLen, bc);
generateGS(needle, ptnLen, gs);

int i = 0;
while (i <= len - ptnLen) {
int j = ptnLen - 1;
while (j >= 0 && needle.charAt(j) == haystack.charAt(i + j)) {
j--;
}
if (j < 0) {
return i;
}
i += Math.max(j - bc[haystack.charAt(i + j)], gs[j]);
}
return -1;
}
}

算法分析:

  • 时间复杂度:O(n / m)
  • 空间复杂度:O(m)

Sunday 算法

简介:Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。其核心思想是:在匹配过程中,模式串发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率

与 BM 算法不同的是,Sunday 算法是从前往后匹配

当发现文本串与模式串不匹配时,关注的是文本串中参加匹配的字符串末位的下一位,这是得分两种情况

CASE 1:该位字符没出现模式串中

索引 0 1 2 3 4 5 6 7 8 9
文本串 a b e a e b a b c d
模式串 a b c d

我们从头开始匹配,在索引2处,发现文本串与模式串不匹配,那么我们关注的就是文本串的索引4处的字符e

很显然,e并没有在模式串中出现,所以我们把模式串整体后移4位,得到

索引 0 1 2 3 4 5 6 7 8 9
文本串 a b e a e b a b c d
模式串 a b c d

CASE 2:该位字符出现在模式串中

继续上一个例子,我们发现,移动后得模式串还是不能与文本串匹配,这是我们关注文本串索引8处的字符c,发现其在模式串中出现了

于是,我们以如下方式移动模式串

索引 0 1 2 3 4 5 6 7 8 9
文本串 a b e a e b a b c d
模式串 a b c d

很显然,此时已经完成了匹配

算法实现

以模式串abcdab为例,逐个列出其每一个对应字符匹配时需要移动的距离

索引 字符 移动距离
0 a 6
1 b 5
2 c 4
3 d 3
4 a 2
5 b 1

可以看出,若是有重复元素应该取后出现的,所以应该从头遍历模式串,就比如ab应该去覆盖后的值21

代码如下

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
class Solution {
private static final int SIZE = 256;

public int strStr(String haystack, String needle) {
int len = haystack.length();
int ptnLen = needle.length();
if (ptnLen == 0) {
return 0;
}

// 移动步长数组 sunday[]
int[] sunday = new int[SIZE];
for (int i = 0; i < SIZE; i++) {
sunday[i] = ptnLen + 1;
}
for (int i = 0; i < ptnLen; i++) {
sunday[needle.charAt(i)] = ptnLen - i;
}

int i = 0;
while (i <= len - ptnLen) {
int j = 0;
while (j < ptnLen && haystack.charAt(i + j) == needle.charAt(j)) {
j++;
if (j == ptnLen) {
return i;
}
}
// 判断是否越界
if (i + ptnLen >= len) {
return -1;
}
// 移动模式串
i += sunday[haystack.charAt(i + ptnLen)];
}
return -1;
}
}

算法分析:

  • 时间复杂度:
    • 最好情况:O(n / m)
    • 平均情况:O(n)
    • 最坏情况:O(n * m)
      (当模式串为aaaaa时,每次只能移动一位,退化为 BF 匹配)
  • 空间复杂度:O(m)