本文共 1793 字，大约阅读时间需要 5 分钟。

转载

1 BF 暴力解法

基本思想：

从目标串s的第一个字符开始，与模式串ss的第一个字符比较。如果相等，则继续比较后续字符；如果不相等，则将s的下一个字符与ss的第一个字符比较。这样反复进行，直到ss中的每个字符依次与s中的一个连续的子串相等。匹配成功时，ss在s中的起始位置即为ss的位置；否则，匹配失败。这种方法效率较低，因为每次不匹配时都需要从头开始比较。

2 KMP 算法

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我们想知道它是否包含另一个字符串"ABCDABD"。

1. 首先，比较字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符。由于字符B与A不匹配，搜索词需要后移一位。 2. 继续比较，字符B与A仍不匹配，搜索词再次后移一位。 3. 这样的过程继续下去，直到找到一个字符与搜索词的第一个字符相同为止。 4. 一旦找到一个匹配字符，继续比较下一个字符是否也匹配。如字符C与B不匹配，搜索词再次后移一位。 5. 这样的逐个比较方式效率很低，因为每次不匹配时都要从头开始比较，这种方法称为暴力解法。

为了提高效率，KMP算法引入了部分匹配表。部分匹配表的作用是记录字符串的前缀和后缀的最大共享子串长度。

例如，对于字符串"ABCDABD"，我们需要构建前缀和后缀的最大共享子串。通过对比可以发现，前缀"A"和后缀"A"的最大共享子串长度为1；前缀"AB"和后缀"BC"的最大共享子串长度为0；前缀"ABCDAB"和后缀"CDAB"的最大共享子串长度为2。

在实际应用中，当字符不匹配时，KMP算法通过查找部分匹配表，确定需要向前移动多少位，从而避免重复比较已经检查过的字符，提高效率。

具体来说，假设在某个位置字符不匹配，已匹配的字符数为6，对应的部分匹配值为2。根据公式，移动位数=已匹配字符数-部分匹配值=6-2=4。因此，搜索词将向后移动4位，继续比较后续字符。

这种方法通过预先计算部分匹配表，使得每次不匹配时能够快速定位到下一个可能匹配的位置，从而显著提高了字符串匹配的效率。

KMP算法的实现步骤如下：

1. 预处理模式串，构建部分匹配表。 2. 使用部分匹配表进行字符串匹配，避免重复比较，提高效率。

以下是KMP算法的实现代码示例：

```cpp #include

#include

#include

using namespace std; void cal_next(string &str, vector

&next) { const int len = str.size(); next[0] = -1; int k = -1; int j = 0; while (j < len - 1) { if (k == -1 || str[j] == str[k]) { ++k; ++j; next[j] = k; } else { k = next[k]; } } } vector

KMP(string str1, string str2, vector

&next) { vector

vec; cal_next(str2, next); int i = 0, j = 0; int str1_size = str1.size(); int str2_size = str2.size(); while (i < str1_size && j < str2_size) { if (j == -1 || str1[i] == str2[j]) { ++i; ++j; } else { j = next[j]; } if (j == str2_size) { vec.push_back(i - j); j = -1; } } return vec; } int main(int argc, char const *argv[]) { vector

vec(20, 0); string str1, str2; cin >> str1; cin >> str2; vector

vec_test = KMP(str1, str2, vec); for (int num : vec_test) { cout << num << endl; } } ```