算法字符串

字符串精确匹配BM算法的变种：Sunday算法

字数统计: 970字   |   阅读时长: 4分
, , ,

摘要: BM算法的变种，Sunday算法

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

在上一篇文章 字符串精确匹配的BM算法 中，我们介绍了字符串精确匹配的 BM 算法。在实际应用的经验中，BM 算法比 KMP 算法快一倍左右。而 BM 算法也有很多变种，应用最成功的是对原始的 BM 算法高度简化后的。因此我们对 BM 算法的一些变种和改进思路感兴趣。

本文我们看 BM 算法的两个变种：Sunday 算法。

sunday 算法

Sunday 在 BM 的基础上做了一些改动。1990 年 Daniel M.Sunday 提出。论文名称为《A Very Fast Substring Search Algorithm》，可以通过下面的链接下载。

《A Very Fast Substring Search Algorithm》

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 + shift[c]，其中 shift 为偏移表，否则，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;
        }
    }
};
Share