字符串匹配（BF KMP）详解 + 刷题

🌼前言

BF 算法

KMP 算法

（1）前缀函数 -- O(n^3)

（2）前缀函数 -- O(n^2)

（3）前缀函数 -- O(n)

（4）辅助理解

🐋P1308 -- 统计单词数

AC -- s.find()

AC -- BF暴力

🦁P3375 -- KMP字符串匹配

🌼前言

以下链接里的代码，最好自己敲一遍，再去刷题

BF 算法

字符串基础👇

字符串基础 - OI Wiki (oi-wiki.org)

BF算法👇

字符串匹配 - OI Wiki (oi-wiki.org)

BF 代码

最好 O(n)，最坏 O(nm)

/*
s 主串      t 模式串(子串)      n 主串长度      t 子串长度
*/
std::vector<int> match(char *s, char *t, int n, int m) {std::vector<int> ans; // 主串匹配成功的第 1 个下标int i, j;for (i = 0; i < n - m + 1; ++i) { // 主串每个位置for(j = 0; j < m; ++j) if (s[i + j] != t[j]) break;if (j == m) ans.push_back(i); // 某个子串匹配成功}return ans; // 返回值类型是 vector<int>
}

KMP 算法

解释

字符串匹配的KMP算法 - 阮一峰的网络日志 (ruanyifeng.com)

初始， "A" 的共有元素长度为 0，因为必须是真前缀和真后缀，不能是本身

补充理解👇

KMP 有 2 种解释（原理都是，真前缀和真后缀，最大共有长度 ---- 即部分匹配值）

解释（1）

部分匹配值，比如说，2，那么子串，要向后移动 m - 2 个位置

m 是子串长度，6 - 2 == 4，对应上面的例子就是👇

解释（2）

部分匹配值 2，那么主串下标 i 不变，子串下标 j 从 2开始

（即，主串下标 i O(n) 线性往后移动，j 每次从前缀函数的位置开始，即 pi[i] 开始，不用从头开始）

意思是，还是👆的图：主串 i 位于 C 的位置，子串就从 "ABCDABD" 中，下标为 2 的位置开始继续比较，即"ABC"的C（等价于上面的子串右移 4 个位置）

代码

前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)

👆 代码是前缀函数的代码，即 “解释” 中的 部分匹配值 的代码

KMP 代码

（1）前缀函数 -- O(n^3)

比如 "ABCDABD"，返回的 pi[3] 表示 "ABCD" 中，前后缀的最大共有长度（不包括ABCD本身）

注：前缀函数，是 KMP 算法的一部分

s.substr(i ,j) 下标 i 开始截取长度为 j 的子串

vector<int> prefix_function(string s) {int n = (int)s.length();vector<int> pi(n); // 最大共有长度for (int i = 1; i < n; ++i) // i 是下标，1 ~ n - 1for (int j = i; j >= 0; --j) // 模式串长度if (s.substr(0, j) == s.substr(i - j + 1, j)) { // 前缀 == 后缀pi[i] = j; // 0 ~ i 的最大共有长度break; // 因为 j 递减, 第一个取到的一定最大}return pi;
}

因为 s.substr() 函数，也是线性复杂度，所以 $O(n^{^{3}})$

i 从 1 开始，因为最大共有长度，不能是本身

（2）前缀函数 -- O(n^2)

比较难理解的是，s[i + 1] = s[pi[i]]

这个需要结合前面两个例子理解

新增的字符，需要在前面前缀的基础上

才可能实现，最大相同长度 + 1

首先你得搞懂，vecotr<int> pi(n) 存的是什么

pi[i] 保存的是 0 ~ i，真前后缀的最大相同的长度

由于主串下标 i 移动到下一位置时，如果前缀函数 pi[] 的值要增加，

最多只能 +1（因为新增的字符，一定是在前面前缀的基础上的）

所以长度 j 只需要从 pi[i - 1] + 1 开始遍历，从上一个位置，最大相同长度 + 1 开始

又 ∵ j--，长度 j 是递减的，pi[i - 1] + 1，是长度 j 可能的最大值

所以只需要修改 j = i --> j = pi[i - 1] + 1 即可

相当于对 p[i - 1] + 1 到 i 这段的剪枝，这一部分是不必要的

vector<int> prefix_function(string s) {int n = (int)s.length();vector<int> pi(n);for (int i = 1; i < n; ++i) // 下标从 1 到 n-1for (int j = pi[i - 1] + 1; j >= 0; --j) // 剪枝if (s.substr(0, j) == s.substr(i - j + 1, j)) {pi[i] = j;break;}return pi;
}

考虑到 j = pi[i - 1] + 1，对长度的限制，以及长度 j 是递减的

每次只有在最好的情况 pi[i - 1] + 1，比较次数上限才会 +1

而每次超过 1 次的比较，都会消耗之后的比较次数

所以计算前缀函数，只需要 O(n) 次比较，总的时间复杂度 $O(n^{2})$

（3）前缀函数 -- O(n)

s[0 ... i] ，下标从 0 到 i 的子串

s[0 ... j - 1] = s[i - j + 1 ... i] ，前缀 = 后缀，长度都为 j

划线部分不是很理解，其他都理解了，，最后得到 状态转移方程，来降低复杂度

下面是代码部分👇

注意这里的 s 是子串

   vector<int> prefix_function(string s) {int n = (int)s.length();vector<int> pi(n);for (int i = 1; i < n; ++i) {// 下标 1 ~ n-1// j 表示 长度int j = pi[i - 1]; // 上一个位置的前缀函数值（最大长度）// 状态转移，退出循环时：//（1）一直失配，直到 j = 0//（2）匹配成功while (j > 0 && s[i] != s[j]) j = pi[j - 1]; // 一直回溯if (s[i] == s[j]) j++; pi[i] = j; // 当前前缀函数值}
}

解释下第 12 行

if (s[i] == s[j]) j++;

👇这里的 i 即上一个 j

例如，假设 s[0...i-1] 的前缀函数值为 j，即 pi[i-1] = j。当 s[i] 和 s[j] 相等时，我们可以将前缀函数长度增加 1，即 j++。然后将新的前缀函数长度 j 赋值给 pi[i]，表示 s[0...i] 的前缀函数值为 j

（4）辅助理解

关于，为什么 KMP 的复杂度是 O(n + m)，详细解释👇

即，为什么子串中，下标 j 不是要回溯吗，为什么复杂度只是本身的长度 m 呢

字符串处理 - KMP算法的时间复杂度是如何计算的？ - SegmentFault 思否

🐋P1308 -- 统计单词数

一般代码中的 next[] 数组，即上面的 pi[] 数组

P1308 [NOIP2011 普及组] 统计单词数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

AC -- s.find()

前置

（1）std::string::npos
#include<iostream>
#include<cstring>
using namespace std;int main()
{string s1 = "babajiaoni";string s2 = "bajiao";string s3 = "babb";if(s1.find(s3) == string::npos) //找不到子串cout<<"找不到子串"<<endl;if(s1.find(s2) != string::npos) //能找到子串cout<<"能找到子串";return 0;
}
（2）

（3）cppreference

pos -- 查找的起始位置

字符串 s 中，下标从 5 开始查找 "is"

返回

Position of the first character of the found substring or npos if no such substring is found

返回子串中第一个字符的位置（主串中），找不到则返回 npos

AC 代码

#include<iostream>
#include<cstring>
#include<string>
using namespace std;int main()
{string t, s;getline(cin, t);getline(cin, s); // 读入一行（包括空格）// 匹配独立的单词，加上空格，便于 find() 匹配t = ' ' + t + ' '; s = ' ' + s + ' ';// 统一变小写int k = 'a' - 'A';// 三目   ? :for (string::size_type i = 0; i < s.length(); ++i)s[i] = (s[i] < 'a' && s[i] != ' ') ? (s[i] + k) : s[i];for (string::size_type i = 0; i < t.length(); ++i)t[i] = (t[i] < 'a' && t[i] != ' ') ? (t[i] + k) : t[i];// 或者用tolower(t[i])    大写 toupper(t[i])if (s.find(t) == string::npos) { // 匹配失败cout << -1;return 0;}int ans = 0, s_pos = s.find(t); // s 中 t 第一次出现的位置int temp = s_pos; // 初始位置while (s_pos != string::npos) {ans++;s_pos = s.find(t, s_pos + 1); // 下一位置开始查找}    cout << ans << " " << temp;// npos 是它能容纳的最大正值，常表示字符串结束return 0;
}

AC -- BF暴力

#include<iostream>
#include<vector>
using namespace std;int main()
{string t, s;getline(cin, t);getline(cin, s); // 读入一行（包括空格）// 统一变小写int k = 'a' - 'A';// 三目   ? :for (string::size_type i = 0; i < s.length(); ++i)s[i] = (s[i] < 'a' && s[i] != ' ') ? (s[i] + k) : s[i];for (string::size_type i = 0; i < t.length(); ++i)t[i] = (t[i] < 'a' && t[i] != ' ') ? (t[i] + k) : t[i];// 或者用tolower(t[i])    大写 toupper(t[i])vector<int> ans; // 保存答案int n = s.length(), m = t.length(), i, j;for (i = 0; i < n - m + 1; ++i) {for (j = 0; j < m; ++j) {if (i > 0 && s[i - 1] != ' ') break; // 空格开头if (s[i + j] != t[j]) break; // 匹配失败}// 空格结尾if (j == m && (s[i+j] == ' ' || i+j == n) )ans.push_back(i);}if (ans.empty()) cout << -1;elsecout << ans.size() << " " << ans[0];return 0;
}

🦁P3375 -- KMP字符串匹配

P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

坑😫

注意，OI -wiki 的代码没问题，不要因为看了大佬阮一峰的文字解释，就误认为，可以 j = pi[j]

熟记状态转移方程，j = pi[j - 1] 即可
else j = pi[j - 1];和j = pi[j - 1]; // 回溯到最大匹配的位置

AC 代码

#include<iostream>
#include<vector>
using namespace std;int cnt = 1; // 测试string s, t;
int pi[1000010]; // 部分匹配数组// 预处理 next数组 复杂度 O(m)
void prefix(string s) // 前缀函数, 子串 -- 最大共有长度
{int m = s.size();for (int i = 1; i < m; ++i) {int j = pi[i - 1]; // 上一位置的部分匹配值// 一直回溯  直到 j == 0 或 匹配成功while (j > 0 && s[i] != s[j]) j = pi[j - 1]; // 状态转移if (s[i] == s[j]) j++;pi[i] = j; // 更新当前匹配值}
}int main()
{cin >> s >> t;int n = s.size(), m = t.size();int i = 0, j = 0;prefix(t);// 主串 与 子串 比较while (i < n) {if (j == 0 && s[i] != t[j]) {i++;continue;}if (s[i] == t[j]) i++, j++;else j = pi[j - 1]; if (j == m) { // 匹配到子串最后一个字母cout << i - j + 1 << endl; // 下标 1 开始j = pi[j - 1]; // 回溯到最大匹配的位置}// cout << "(" << cnt++ << ")" <<i << " " << j << endl;}// 输出 pi[]for (i = 0; i < m; ++i)cout << pi[i] << " ";return 0;
}