(一) KMP模板
优化思路
先打暴力,从过程中发现重复的操作,进行优化。
一、暴力 O(mn)
枚举字符串中每一个位置作为模式串的起点,尝试匹配。
核心代码:
for (int i = 1; i <= m; i ++ )
{
bool flag = true;
for (int j = 1; j <= n; j ++ )
if (s[i + j - 1] != p[j])
{
flag = false;
break;
}
if (flag) cout << i - 1 << " ";
}
二、优化
我们发现,如果当前尝试行不通,我们之前已经在第二重循环中扫过的区域有很大一块会再次被扫到。如图
那么KMP就是通过一些空间消费,优化了这一块,使得我们可以通过预处理的信息将模式串的位置直接移到下一个合理的位置
1.利用预处理优化算法
在一次枚举匹配中,对于模式串从开头到最后一个正确的位置(也就是紫竖线之前的那一块,下称大区间),如果我们能够从大区间中找到两个小区间,保证两个小区间是完全相等的,并且第一个区间的开头是模式串的开头,第二个区间的结尾是大区间的结尾(也就是紫竖线前最后一个可以匹配的元素),那么我们可以将模式串的开头“移”(以下记此操作为平移)到第二个区间的开头(也就是让整个模式串跟着第一个区间平移到了第二个区间),形成下一次匹配的情形。
此时,我们无需判断新情形中紫竖线前面的一块是否符合要求。从而避免了重复的“扫”。
至于为什么无需判断,我们看到第二个区间一定符合字符串S的部分区域,而第一个区间和第二个区间又是完全相等的,所以平移过去不会影响这一块的匹配。
而为了不漏所有的可能,我们当然希望每次平移都能够移动较少的距离,也就是说要看大区间内第一、第二区间的最长长度(自行模拟可知)。
而KMP就是来预处理这样的信息。
next[i]就是来储存模式串p中从下标 1 (即模式串开头)到下标 i 这个大区间中第一、第二区间的最大长度。
即:
next[i] 储存的是满足 p[1, j]=p[i−j+1, i] 的 j 的最大值
2.怎么求 next[i] 呢?
我们按照顺序从模式串中从左到右求 next[i] ,就可以使用前面已经处理过的 next 值了。
我们尝试使用 next[i−1] 增值到 next[i]
如图:
如果相等,那么 next[i] 就出来了。
如果不相等,我们继续缩小考察的区间,直到找到相等的。
三、正解 Θ(m+n)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, m;
char p[N], s[N];
int ne[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
// 求 next[i]
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j]; // 不断缩小范围,直到出现相等。
if (p[i] == p[j + 1]) j ++; // 这里 j 就是当前第一第二区间的长度了。因为 j 有可能变为 0,所以这里要判断。
/* 出现相等,那么 第一第二区间可以吸收 p[j + 1] 和 p[i],于是 j ++ 。
同时为下一步查找奠定查找范围 j 的基础。 */
ne[i] = j; // 记录 next[i]。
}
// 匹配
for (int i = 1, j = 0; i <= m; i ++ ) // 为字符串中第 i 个元素匹配元素。
{
while (j && s[i] != p[j + 1]) j = ne[j];
/* 当找到字符串和模式串不能互相匹配的地方时,
就不断的平移变换(将模式串向右“移”),直到可以匹配。
*/
if (s[i] == p[j + 1]) j ++; // 这里 j 就是能够匹配 i 的第一第二区间最大长度。判断理由同上。
if (j == n) // 匹配成功。
{
printf("%d ", (i - n + 1) - 1); // -1 因为题目以 0 开始记录。
j = ne[j]; // 还是继续平移,而不是 j ++
}
}
return 0;
}