KMP学习笔记
简述
前言
KMP（Knuth–Morris–Pratt）算法是一种高效的查找子串的算法，设有一个长度为 的文本 和一个长度为 的字符串 ，她可以在 的空间复杂度和 的时间复杂度求出所有 在 中出现的所有位置，是AC自动机的一个前置芝士
引入
前缀函数
定义
（下文摘自OI Wiki）
给定一个长度为 的字符串 ，其前缀函数被定义为一个长度为 的数组
其中 ：
- 如果子串 有一对相等的真前缀与真后缀： 和 ，那么
- 如果不只有一对相等的，那么 就是其中最长的那一对的长度
- 如果没有相等的，
数学语言如下：
特别的，
实现
1
2
3
4
5
6
7
8
9
10
11
| vector<int> prefix_function(string s) {
int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
|
实现
对于一个长度为 的文本 和一个长度为 的字符串 ，构造一个字符串 ，其中 为一个既不出现在 中也不出现在 中的分隔符，接下来计算前缀函数
由前缀函数的定义可得，若 成立，则意味着 完整出现在该位置
这就是KMP算法的大致原理，示例代码如下（需要搭配上文prefix_function食用）：
1
2
3
4
5
6
7
8
9
10
| vector<int> find_occurrences(string text, string pattern) {
string cur = pattern + '#' + text;
int sz1 = text.size(), sz2 = pattern.size();
vector<int> v;
vector<int> lps = prefix_function(cur);
for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
if (lps[i] == sz2) v.push_back(i - 2 * sz2);
}
return v;
}
|
练习
模板
Luogu P3375 【模板】KMP
模板，用标准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
| #include <bits/stdc++.h>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la, lb, j;
char a[MAXN], b[MAXN];
int main() {
cin >> a + 1;
cin >> b + 1;
la = strlen(a + 1);
lb = strlen(b + 1);
for (int i = 2; i <= lb; i++) {
while (j && b[i] != b[j + 1])
j = kmp[j];
if (b[j + 1] == b[i])j++;
kmp[i] = j;
}
j = 0;
for (int i = 1; i <= la; i++) {
while (j > 0 && b[j + 1] != a[i])
j = kmp[j];
if (b[j + 1] == a[i])
j++;
if (j == lb) {
cout << i - lb + 1 << endl;
j = kmp[j];
}
}
for (int i = 1; i <= lb; i++)
cout << kmp[i] << " ";
return 0;
}
|
例题1
CodeForces 1200E Compress Words
还没有写到这里哦
