KMP
信息学奥赛一本通
模板
AcWing
// 下标从1开始
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j]; // j = 0;
// 匹配成功后的逻辑
}
}
注意：16行的 j = ne[j] 是可重叠的情况。
如果换成 j = ne[j] 是不可重叠的情况。
自己的
// 下标从1开始
void init() {
for (int i = 1, j = 0; i <= n; i ++ ) {
while (j && p[i + 1] != p[j + 1]) j = ne[j];
if (p[i + 1] == p[j + 1]) j ++ ;
ne[i + 1] = j;
}
}
void Solve() {
for (int i = 0, j = 0; i <= m; i ++ ) {
while (j && s[i + 1] != p[j + 1]) j = ne[j];
if (s[i + 1] == p[j + 1]) j ++ ;
if (j == n) {
cout << i + 1 - n << " "; // 匹配成功后的逻辑
j = ne[j]; // j = 0;
}
}
}
注意：14行的 j = ne[j] 是可重叠的情况。
如果换成 j = ne[j] 是不可重叠的情况。
题目
题目1
模板题 - 可重叠 - luogu P3375 【模板】KMP 字符串匹配
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m; // n主串长度
char s1[N], s2[N]; // s1主串
int ne[N];
int main() {
cin >> s1 + 1 >> s2 + 1;
n = strlen(s1 + 1), m = strlen(s2 + 1);
for (int i = 1, j = 0; i <= m; i ++ ) {
while (j && s2[i + 1] != s2[j + 1]) j = ne[j];
if (s2[i + 1] == s2[j + 1]) j ++ ;
ne[i + 1] = j;
}
for (int i = 0, j = 0; i <= n; i ++ ) {
while (j && s1[i + 1] != s2[j + 1]) j = ne[j];
if (s1[i + 1] == s2[j + 1]) j ++ ;
if (j == m) {
cout << i + 1 - m + 1 << endl;
j = ne[j];
}
}
for (int i = 1; i <= m; i ++ )
cout << ne[i] << " ";
return 0;
}
题目2
其他题目 - 不可重叠 - LibreOJ #10043. 「一本通 2.2 例 1」剪花布条
题目可以转化为给定字符串 s1 和 s2，求申 s1 中可以分割出多少个互不重叠的串 s2。
直接用 KMP 算法即可，注意计算不重叠的匹配个数。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
char s1[N], s2[N]; // s1 是主串
int ne[N], ans;
int main() {
while (true) {
cin >> s1 + 1;
n = strlen(s1 + 1);
if (s1[1] == '#' && n == 1) break;
cin >> s2 + 1;
m = strlen(s2 + 1);
// 初始化 ne 数组
for (int i = 1, j = 0; i <= m; i ++ ) {
while (j && s2[i + 1] != s2[j + 1]) j = ne[j];
if (s2[i + 1] == s2[j + 1]) j ++ ;
ne[i + 1] = j;
}
// 匹配过程
ans = 0;
for (int i = 0, j = 0; i <= n; i ++ ) {
while (j && s1[i + 1] != s2[j + 1]) j = ne[j];
if (s1[i + 1] == s2[j + 1]) j ++ ;
if (j == m) {
ans ++ ;
j = 0; // 从头开始重新匹配，保证不重叠
}
}
cout << ans << endl;
}
return 0;
}