目录
  1. 1. 字符串匹配02 - Sunday 算法
    1. 1.1. 思路
    2. 1.2. 代码实现
    3. 1.3. 算法分析
字符串匹配02 - Sunday 算法

字符串匹配02 - Sunday 算法

问题:

​ 给定字符串 SS 和模板字符串 TT , 求 TT 是否在 SS 中出现过, 如果有, 则返回 TTSS 中第一次出现的位置.

在上一篇中我们讲到,暴力求解虽然很容易实现,也很容易理解,在随机字符串和随机模板串的表现也不错,但毕竟这个算法属于平方阶,算法规模增长的太快了,我们仍然需要更优秀的算法, 本篇我们将介绍Brute ForceBrute \space Force 算法的一种改进, SundaySunday 算法

思路

首先我们来思考一下为什么Brute ForceBrute \space Force算法的局限在哪里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int brute_force_match(const std::string &S, const std::string &T) {
int n = S.length();
int m = T.length();

for (int i = 0; i <= n - m; ++i) {
for (int j = 0; j < m; ++j) {
if(S[i + j] != T[j])
break;
if (j == m - 1)
return i;
}
}

return -1;
}

我们可以看到,当我们匹配失败后,Brute ForceBrute \space Force 只是单纯的将游标向后移了一位,并没有利用匹配失败或成功的信息

SundaySunday 算法正是关注了在不匹配情况下,尽可能跳过多的字符, 从而提高了匹配效率

即关注匹配失败时,参加匹配的最末位字符的下一位字符,如果该字符没有在模板串中出现过,则移动步长=模板串长度 +1,否则,移动步长=匹配串中该字符最右端出现的位置到匹配串末尾的位置 + 1

next={max{mi+1},Ti=chm+1,otherwisenext = \begin{cases} max\{m - i + 1\}, T_i = ch \\ m + 1, otherwise \end{cases}

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int sunday_match(const std::string &S, const std::string &T) {
int n = S.length();
int m = T.length();

int next[CHAR_TABLE_SIZE];

for (int &i : next)
i = -1;

for (int i = 0; i < m; ++i)
next[T[i]] = i;

int p = 0;
int j;
while (j = 0, p <= n - m) {
while (S[p + j] == T[j]) {
if (++j == m)
return p;
}
p += (m - next[S[p + m]]);
}

return -1;
}

算法分析

平均时间复杂度为O(n)\Omicron(n),最坏时间复杂度为O(nm)\Omicron(nm)

文章作者: Twiliness
文章链接: https://twiliness.xyz/2019/10/07/String-Matching-02-Sunday/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Twilight Spring