BF（Brute Force）算法#

BF算法最容易理解，也是最暴力的方法

简单来说，就是从模式串中一个字符一个字符地进行比较

当发现不匹配的时候，回退到模式串开头并重新匹配

BF 算法示意动图

那么我们可以写出代码：

1
int BFSearch(std::string source, std::string pat) {
2
    if (source.size() < pat.size()) return -1;
3

4
    int j = 0;
5
    for (int i = 0; i <= source.size() - pat.size(); i ++) {
6
        j = 0;
7
        while (source[i + j] == pat[j] && j < pat.size()) {
8
            j ++;
9
        }
10
        if (j == pat.size()) return i;
11
    }
12

13
    return -1;
14
}

首先，匹配需要保证我们的源串长度大于模式串长度，否则在后续匹配的 source.size() - pat.size() 会出现问题

之后，我们维护一个变量 $j$，它表示当前模式有多少个字符是匹配的；举个例子：

当有情况：

1
source: ABCDABC
2
pat:    ABD

那么进行匹配到 source[2] 的时候，此时由于源串的前两个字符 AB 和模式串的前两个字符是匹配的，所以此时有 $j = 1$

而对于这个循环，只要 $j$ 指示的对应模式的字符和源串对应位置的字符是相等的，就说明匹配成功，此时也就有 $j = j + 1$

NOTE

对于 $source[i + j]$，这里的 $j$ 可以看作是一个相对于当前源串指针 $i$ 的一个偏移量

最后，如果这一次 for 循环中，$j$ 满足 $j = pat.size()$，就说明模式被完全匹配，那么就可以返回最开始匹配的索引 $i$

KMP算法#

注意到BF算法有一个弊端：只要模式有不匹配的部分就会将整个匹配进度回退到开头；但是有的模式串有一些相同的部分，在确定这部分是匹配的情况下，直接将整个进度回退到开头会造成一些时间上的损失；为了让整个查找过程更加的迅速，更好的方案是使用KMP算法

很明显，对于一个模式串，其重复的那一部分如果被匹配到了，之后如果发生了模式失配，没有必要像BF算法一样将整个匹配进度回退，而是应该查找是否有一部分可以直接作为下一轮匹配的开头，并继续匹配

这时候，我们需要维护一个数组 $next$，用于计算当模式失配的时候我们应该将匹配进度回退到何处

为了更好地介绍如何建立 $next$ 数组，现在介绍下面的一些概念：

1
ABCDA
2

3
前缀：
4
A
5
AB
6
ABC
7
ABCD
8

9
后缀：
10
A
11
DA
12
CDA
13
BCDA

1
ABABA
2

3
前缀：
4
A
5
AB
6
ABA
7
ABAB
8

9
后缀：
10
A
11
BA
12
ABA
13
BABA

1
pat: ABABC

1
std::vector<int> buildNext(std::string pat) {
2
    std::vector<int> next(pat.size(), 0);
3
    int j = 0;
4
    for (int i = 1; i < pat.size(); i ++) {
5
        while (j > 0 && pat[j] != pat[i]) {
6
            j = next[j - 1];
7
        }
8

9
        if (pat[j] == pat[i]) j ++;
10

11
        next[i] = j;
12
    }
13
    return next;
14
}

1
while (j > 0 && pat[j] != pat[i]) {
2
    j = next[j - 1];
3
}

1
j = next[j - 1];

1
if (pat[j] == pat[i]) j ++;

1
int KMPSearch(std::string source, std::string pat) {
2
    auto next = buildNext(pat);
3

4
    int j = 0;
5
    for (int i = 0; i < source.size(); i ++) {
6
        while (j > 0 && source[i] != pat[j]) {
7
            j = next[j - 1];
8
        }
9

10
        if (source[i] == pat[j]) j ++;
11

12
        if (j == pat.size()) {
13
            return i - pat.size() + 1;
14
        }
15
    }
16

17
    return -1;
18
}

1
if (source[i] == pat[j]) j ++;

BF算法和KMP算法的性能比较#

基于上面的代码，写出测试代码：

1
int main() {
2
    std::string A = "OGenshinImpactOdwrgwrgGenshinImpactOGenshinImpactOgergGenshinImpactLPF.DF;.[.#@$@@FFBUBV]FGJCOMVONonvonbe#@$$??gbbjpjov---vdfbseblplfgggVONonvonpppPP";
3
    std::string B = "FGJCOMVON";
4
    auto bfStart = std::chrono::steady_clock::now();
5
    std::cout << BFSearch(A, B) << std::endl;
6
    auto bfEnd = std::chrono::steady_clock::now();
7
    std::cout << "BFSearch, cost: " << std::chrono::duration_cast<std::chrono::microseconds>(bfEnd - bfStart).count() << "us" << std::endl;
8

9

10
    auto kmpStart = std::chrono::steady_clock::now();
11
    std::cout << KMPSearch(A, B) << std::endl;
12
    auto kmpEnd = std::chrono::steady_clock::now();
13
    std::cout << "KMPSearch, cost: " << std::chrono::duration_cast<std::chrono::microseconds>(kmpEnd - kmpStart).count() << "us" << std::endl;
14
}

运行结果：

1
89
2
BFSearch, cost: 113us
3
89
4
KMPSearch, cost: 43us

可以看出来，KMP算法的效率明显高于BF算法

对于 BF 算法，考虑最坏情况：模式串直到源串结尾附近才出现，并且在此前的每一次匹配中，模式串都能够匹配较长的前缀后才发生失配。每次匹配失败后，模式串向后移动一个位置，并重新从模式串的第一个字符开始比较。

此时，每一个可能的匹配起点最多需要比较 $m$ 次，而源串中能够作为匹配起点的位置一共有 $n-m+1$ 个。

因此，最坏情况下的比较次数最多为：

忽略低阶项后，其时间复杂度为：

而对于 KMP 算法，由于使用 $next$ 数组保存了模式串的前缀与后缀之间的匹配关系，因此发生失配时无需重新从模式串的起点开始匹配，而是通过 $next$ 数组直接将匹配状态 $j$ 回退到下一个可能的位置。

虽然 KMP 的代码中存在 for 与 while 的嵌套结构，但 $i$ 在整个匹配过程中只向前移动，而 $j$ 的增长和通过 $next$ 进行的回退次数总体上都是线性的。因此，构造 $next$ 数组的时间复杂度为 $O(m)$，实际进行字符串匹配的时间复杂度为 $O(n)$

所以，KMP 算法的总时间复杂度为：

空间复杂度方面，BF 算法只需要常数级的辅助变量，因此为 $O(1)$；KMP 需要额外保存长度为 $m$ 的 $next$ 数组，因此空间复杂度为 $O(m)$