本文将重点阐述字符串中的KMP模式匹配算法。

本文代码放置在Github处。

BF 算法

不多赘述了，给一个简要的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> bf_search(const string &text, const string &pattern)
{
    vector<int> result;
    int text_len = text.length();
    int pattern_len = pattern.length();
    for(int i=0; i < text_len-pattern_len+1; i++)
    {
        for(int j=0; j < pattern_len; j++)
        {
            if(text[i+j] != pattern[j])
            {
                break;
            }
            if(j == pattern_len-1)
            {
                result.push_back(i);
            }
        }
    }
    return result;
}

KMP 算法

本文重点在KMP算法, 但请注意, 国内网站与本课程教科书都是写的一个 next 数组, 而国外则比较常用 lps 数组, 两者的表示略有区别. 本文将使用 lps 数组.

预准备 - lps 数组

先介绍一下LPS是什么, LPS (the Longest Prefix Suffix), 就是最长的公共前缀和后缀.

与 next 数组不同, next 记录 j 指针回退的位置, 而 lps 则只是记录对应字符串的最长公共前后缀长度.

最长公共前后缀到底有什么用呢? 其实就是减少j指针回退的次数, 原本i, j都需要回退, 而在KMP算法中, 只需要回退j, 因为我们只要找到模式串中可以与i之前的字符匹配的公共前缀, 那么就可以直接跳过i之前的字符, 减少回退次数.

也正因如此, 只需要将 j 每次赋值为 lps[j-1] 直至回退到0就行.

接下来, 我们来看下如何求出 lps 数组.

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
// 假设已经包括了头文件 <string> <vector>
vector<int> compute_lps(const string &pattern)
{
    int length = 0; // 前一个LPS的长度
    int i = 1;
    vector<int> lps(pattern.length(), 0);   // 初始化lps数组

    // lps[0] 始终为0, 所以 i 的初始值为1
    while (i < pattern.length())
    {
        if (pattern[i] == pattern[length])
        {
            // 匹配上则更新length和lps[i]
            // 因为pattern[0: length]是和pattern[i-length: i]相同的, 所以只要比较一个值
            length++;
            lps[i] = length;
            i++;
        }
        else
        {
            if (length != 0)
            {
                // 匹配不上, 则回退length, 并且更新lps[i]
                // 这和KMP算法本身也是很相像的
                length = lps[length - 1];
            }
            else
            {
                lps[i] = 0; 
                // 也可以写作 lps[i] = length; 与上面保持统一.
                i++;
            }
        }
    }

    return lps;
}

主算法

算出了 lps 数组, 那么KMP算法实现就显得异常轻松了.

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
vector<int> kmp_search(const string &text, const string &pattern)
{
    vector<int> lps = compute_lps(pattern);
    vector<int> result;

    int i = 0; // index for text[]
    int j = 0; // index for pattern[]
    while (i < text.length())
    {
        if (pattern[j] == text[i])
        {
            // 匹配上就继续
            j++;
            i++;
        }

        if (j == pattern.length())
        {
            // j 匹配到了末尾, 说明找到了一个匹配, 添加到结果中, 并且回退j
            result.push_back(i - j);
            j = lps[j - 1];
        }
        else if (i < text.length() && pattern[j] != text[i])
        {
            // 发生不匹配就回退j
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
            // 当lps的值为0时, 也就是j回退到了0, 则i继续前进, 否则回退j
        }
    }

    return result;
}

这样我们就实现了完整的KMP算法了，其实还是挺简单的。