算法通关(3) -- kmp算法
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：
利用栈，压入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;
}
原文地址：https://blog.csdn.net/2301_79985750/article/details/143572010
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！