算法字符串

字符串精确匹配 | BM算法的变种-Horspool算法

字数统计: 744字   |   阅读时长: 3分
, , ,

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

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

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

在上一篇文章 字符串精确匹配BM算法的变种：Sunday算法 中，我们介绍了 BM 的一个变种即Sunday 算法，本文我们看 BM 算法的另一个变种：Horspool算法。

horspool 算法

Horspool 算法是 BM 算法的一个简化版本，与 BM 一样，也是从右向左比较(Sunday 是从左到右)。该算法由 R. Nigel Horspool 在 1980 年提出，论文名称《Practical Fast Searching in Strings》，可以通过下面的链接下载。

《Practical Fast Searching in Strings》

匹配机制过程

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

  1. b 在 p 中未出现，shift[i] = m (第一次比较就失配 s[i+m-1]!=p[m-1])。
  2. b 在 p 中出现，且 p[i + m - 1] != b，则将 p 中最右边的 b 与 s[i] 对齐
  3. b 在 p 中出现，且 p[i + m - 1] == b，但其余元素中没有 b，与情况 1 一样 (第一次比较就失配 s[i+m-1]!=p[m-1])
  4. b 在 p 中出现，且 p[i + m - 1] == b，其余元素中也有 b，与情况 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);
    }
};
Share