算法字符串

字符串精确匹配

字数统计: 4.3k字   |   阅读时长: 20分
, , ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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 中最右边的 \beta 与 s[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