先来看一个字符串匹配的例子.
- 问题描述, 给两个字符串S和T, 询问T在S中出现了多少次.
- S = ‘’abacabc’‘
- T = ‘’ab’‘
暴力法
- 枚举 $S$ 字符串的每一个位置, 并且尝试匹配.
- 时间复杂度 $O(|S| \cdot |T|)$
KMP法
- 每次匹配失败后, 并不是直接从
0开始重新匹配,而是吸取上一次的经验教训, 从而达到优化时间复杂度的目的. - $KMP$ 算法的核心是 $next$ 数组的求解
- $next[i]$ 前 $i+1$ 个字符(字符串下标从 $0$ 开始), 前缀和后缀相等的最长长度(小于 $i+1$).
- 比如 $ababac$ 这个字符串, $next[2] = 1$, $next[4] = 3$
- 接下来就要快速求解
next数组.
KMP - 为什么是“最大” 子串长度？
- 公共子串长度越小，向右移动的距离越大，越不安全
- 公共子串长度越大，向右移动的距离越小，越安全
next数组的求法
k代表前缀等于后缀的最长长度.- -1. 当
s[k] == s[i]时,next[i] = k+1 - -2. 当
s[k] != s[i]时,k=next[k - 1]寻找一个k的一个前缀,尝试匹配s[i], 如果找不到的话,k = 0 - 有了
next数组之后字符串的匹配就简单了很多.
代码实现
inline void KMP(char *s, int *next) {
int fix = 0;
next[0] = 0;
for (int i = 1; s[i]; ++i) {
while (fix && s[fix] != s[i]) fix = next[fix - 1];
if (s[fix] == s[i]) fix++;
next[i] = fix;
}
}
匹配
- 可以看到, 我们依然枚举
s串匹配的起点, 但是t串开始匹配的长度不一样. - 当
s[i] == t[x]的时候, i可以直接挪到下一位,x++, 但是当s[i] != t[x]的时候, x需要不断回滚,x=next[x - 1],直到t[x] == s[i], 当一次匹配完成之后x不是重新从0开始, 而是x = next[len - 1] - 这样我们就可以快速的求出
t在s中出现的次数
代码实现
int Strstr(char *s, char *t) { // 返回值为t在s中出现了几次
int x = 0, len = strlen(t), ans = 0;
for (int i = 0; s[i]; ++i) {
while (x && s[i] != t[i]) x = next[x - 1];
if (s[i] == t[x]) ++x;
if (x == len - 1) ++ans, x = next[len - 1];
}
return ans;
}
例题：KMP字符串匹配
题目： 【模板】KMP字符串匹配
代码实现：
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::string;
const int N = 1000010;
int next[N];
int main() {
string s1, s2;
cin >> s1 >> s2;
int n = s2.size();
int m = s1.size();
s1 = ' ' + s1, s2 = ' ' + s2;
// 求next过程
for (int i = 2, j = 0; i <= n; ++i) {
while (j && s2[i] != s2[j + 1]) j = next[j];
if (s2[i] == s2[j + 1]) ++j;
next[i] = j;
}
// kmp匹配过程
for (int i = 1, j = 0; i <= m; ++i) {
while (j && s1[i] != s2[j + 1]) j = next[j];
if (s1[i] == s2[j + 1]) ++j;
if (j == n) {
// 匹配成功
cout << i - n + 1 << "\n";
j = next[j];
}
}
for (int i = 1; i <= n; ++i) cout << next[i] << " \n"[i == n];
return 0;
}
