KMP算法的原理
从题目引出
有两个字符串s1和s2,判断s1字符串是否包含s2字符串,如果包含返回s1包含s2的最左开头位置,不包含返回-1,如果是按照暴力的方法去匹配,以s1的每个字符作为开头,用s2的整体去匹配,那么得到的时间复杂度达到O(m*n),若字符串长度过长,那么可能导致不能AC。。。那么可不可以利用前面的匹配过程去帮助匹配加速,某些位置不用按照一个位置一个位置的去匹配。有的,这就是今天要了解的KMP算法。
1.next数组的定义
先知道是怎么回事就行
用s2去匹配s1,next数组是对于s2来说的;含义:不包含当前,它前面字符串前缀和后缀最大匹配长度,也不能包含整体:例如前面的字符串abc,如果包含整体,abc一定匹配abc,没有了意义.
对于0位置的a来说,它的前缀什么都没有,因此放一个-1表示不存在;对于1位置的a来说,前面有一个a,但是只有一个字母,不能够进行匹配,匹配则违反了包含整体(此时整体只有一个1),因此1位置是0;对于2位置b来说,前面是aa,前缀一个a,后缀一个a,刚好匹配,因此填1;
对于3位置的a来说,前面是aab,取一个(前缀是a,后缀是b,不行),取两个(前缀是aa,后缀是ab,不行),因此是0.。。。依次类推,对于6位置的x来说,前面是aabaab,最长匹配字符串是3,因此填3;
同理:对于12位置的a来说,选择5个是最大的匹配长度。 记住,不包含当前下标的字符!!!
2.如何加速匹配?
匹配到13位置不相同,下次位置从哪里匹配?匹配不上的next位置是6,那么让s2的6位置的c去匹配s1的13位置,也就是说,前面的1~6位置被放弃了!!!这里引出两个问题:
1:为什么放弃前面的?2:s2的0~5位置为什么不用验证,可以直接从6位置的c开始和s1的13进行匹配?
第二个问题:
先回答第二个问题:因为next数组是不包含当前,它前面字符串前缀和后缀最大匹配长度,为什么是6,因为那个位置的s2字符串前面数6个和后面数6个得到的字符串相同!!!如图:
由于s1和s2的匹配,可知m1和n1相同,m2和n2相同,又因为next数组,n2和n1相同,那么这四个都相同,就可以得出n1和m2相同,既然相同了,那么就没必要费时间从头开始了。继续匹配如下图:
第一个问题:
四个红色方框长度相同.上面说的是s2从k位置开始匹配,假设可以从小于k的位置进行匹配,例如图中的m位置,因为s1的m位置之后和s2之后的字符相同(不包含j位置,因为是从哪里进行的退出),
从m位置进行匹配可以成功,那么s1的绿色和s2的绿色(下边)一定可以匹配成功,由于s1的绿色第一次匹配时和s2的绿色(上边)匹配成功,因此可以得到s2的这两端绿色是相同的字符串
而这个长度超过了next数组给定的长度,因为只要匹配上,next算的是不包含当前,它前面字符串前缀和后缀最大匹配长度,违背了next记录最大长度。这样子就加速了匹配的进程
3.KMP算法代码
int kmp(const string& s1, const string& s2) {
// x是s1的比对位置
// y是s2的比对位置
int n = s1.length(), m = s2.length(), x = 0, y = 0;
// 获取next数组
vector<int> next = nextArray(s2, m);
// 不越界
while (x < n && y < m) {
if (s1[x] == s2[y]) {
// 每个位置可以匹配的上
x++;
y++;
}
// 当前不等
else if (y == 0) {
// 如果是s2的0位置没有匹配出来,无法往前跳了
// s1换个位置开头吧,s2不动
x++;
}
else {
// s2的其他位置没有匹配出来,按照s2的y位置的next[y]跳跃
// s1不动,s2换个位置配
y = next[y];
}
}
// s2匹配ok了,就找到了
// 越界还没有找的,返回-1
return y == m ? x - y : -1;
}
4.next数组如何快速生成
按照前面的next值求下一个位置的next值
情况1:不用跳
求得“?”位置的next值,看的是前面字符的最大匹配长度,得知是8;也可以看前面“x”位置的next值,是7,看他与7位置的字符是否相同,这里相同,因为不相同就必须跳了,那就+1,得到8,为什么不能够更长呢?如图:
情况2:需要跳
用图来说吧
如果没有对上,继续跳,如果跳到头都没有跳出来,那么要求的next就是0。
为什么这样子,其实找的前缀和后缀都是在s2这个字符串中,即在一个字符串中找到尽可能的长的前缀和后缀,这就是next数组的含义,因为要保留尽量长!!!举个例子
5:next数组代码
vector<int> nextArray(const string& s, int m) {
// m是字符串s2的长度
if (m == 1) {
return { -1 };
}
// next的第一个位置和第二个位置是固定的
vector<int> next(m);
next[0] = -1;
next[1] = 0;
// 从第二个位置开始填
int i = 2, cn = 0;
// 没有越界
while (i < m) {
// i 表示当前要求的next值的位置
// cn表示当前要和一个字符比对的下标
if (s[i - 1] == s[cn]) {
// 后面的字符是cn位置
// 为什么是++cn,而不是cn+1
// 因为为了下面可能用到cn的值,如果后面的字符是cn位置,那么直接用
// 当前位置求完了,求下一个位置就是++
next[i++] = ++cn;
}
else if (cn > 0) {
// 不一样,向前跳
cn = next[cn];
}
else {
// 已经等于0了,再往前跳到-1位置
next[i++] = 0;
}
}
// 得到next数组
return next;
}
KMP算法相关题目
题目1:
P4391 [BOI2009] Radio Transmission 无线传输 - 洛谷 | 计算机科学教育新生态
总长度是k个最短长度(设为n)的字串加上尾巴的一些,尾巴长度为L,那么总长度为k*n+L,前缀最大的长度串是(k-1)*n+L,因为此例中是以a开头,下一个a是经过了一次循环后的a,因此可以得到最大长度串。
两个疑惑:它可以更短吗?不可以,因为next求得就是它前面字符串前缀和后缀最大匹配长度。
它可以更长吗?不可以,举个例子:
因此可以得出结论:不能够变得更短,也不能变得更长!!!
代码如下:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 1000001;
int next_[MAXN];
int n;
string s;
void nextArray() {
next_[0] = -1;
next_[1] = 0;
int i = 2, cn = 0;
while (i <= n) {
if (s[i - 1] == s[cn]) {
next_[i++] = ++cn;
}
else if (cn > 0) {
cn = next_[cn];
}
else {
next_[i++] = 0;
}
}
}
int compute() {
nextArray();
return n - next_[n];
}
int main() {
cin >> n;
cin >> s;
cout << compute() << endl;
return 0;
}
题目2:
[USACO15FEB] Censoring S - 洛谷
利用栈,压入s1位置字符的下标以及s2位置字符的下标。
如果位置字符下标的值对应,那么两个字符向前++,当s2越界了,那么表示s1的一段和s2匹配上了,那么使栈的长度-s2的长度,然后根据栈顶元素的下标,让s2找到正确的下标。如图:
代码如下:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 1000001;
int next_[MAXN];
// 栈1压s1,栈2压s2
int stack1[MAXN];
int stack2[MAXN];
int _size;
string s1, s2;
// 生成s2的next数组
void nextArray(int m) {
next_[0] = -1;
next_[1] = 0;
int i = 2, cn = 0;
while (i < m) {
if (s2[i - 1] == s2[cn]) {
next_[i++] = ++cn;
}
else if (cn > 0) {
cn = next_[cn];
}
else {
next_[i++] = 0;
}
}
}
void compute() {
_size = 0;
int n = s1.length(), m = s2.length(), x = 0, y = 0;
// s2的next数组
nextArray(m);
while (x < n) {
if (s1[x] == s2[y]) {
// 对应的上,s1和s2两者++
stack1[_size] = x;
stack2[_size] = y;
_size++;
x++;
y++;
}
// 对应不上,而且y来到s2的开头位置
else if (y == 0) {
//
stack1[_size] = x;
stack2[_size] = -1;
_size++;
x++;
}
// 对应不上,没来到开头位置,往前跳
else {
y = next_[y];
}
// s2遍历完了
if (y == m) {
// 相当于栈直接弹出了m条记录
_size -= m;
// 处理s2的y
// 栈中有东西,跳到栈顶的下一个位置
// 没有就是0下标
y = _size > 0 ? (stack2[_size - 1] + 1) : 0;
}
}
}
int main() {
cin >> s1 >> s2;
compute();
for (int i = 0; i < _size; i++) {
cout << s1[stack1[i]];
}
cout << endl;
return 0;
}