KMP算法基础
文章一览
- 前言
- 一、核心思想
- 二、实现步骤
- 三、图解实现
- 四、next数组的实现
- 总结
前言
本栏目将讲解在学习过程中遇到的各种常用算法，深入浅出的讲解算法的用法与使用场景。
那么话不多说，让我们进入第一个算法KMP算法吧！
一、核心思想
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串搜索算法，用于在一个文本字符串中搜索一个模式字符串的出现。
它的核心思想是，当不匹配发生时，利用已经匹配的部分信息，避免从头开始搜索，从而提高搜索效率。
借用在B站看到的某位网友的评论：“一个人能能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。”
这就是KMP算法的核心思想，看起来有点迷糊，那么继续往下看，了解了它的基本用法后，相信你会对它有更加深刻的理解。
二、实现步骤
KMP算法的步骤大致如下：
- 模式匹配失败时的处理：
- 通常情况下，当出现不匹配时，模式会向右移动一个位置，重新开始匹配。但KMP算法会利用已经匹配的部分信息，决定模式应该向右移动多远。
- 前缀函数（也称为部分匹配表）：
- KMP算法使用一个被称为“部分匹配表”（next function）的数据结构来记录模式字符串中每个位置之前的子串的最长相同前后缀的长度。这个表帮助算法在出现不匹配时，决定模式字符串应该向右移动多远。
- 搜索过程：
- 遍历文本字符串，将模式字符串与文本字符串进行匹配。
- 如果当前字符匹配成功，则模式字符串向右移动一位。
- 如果出现不匹配，根据部分匹配表，决定模式字符串应该向右移动多远，而不是简单地移动一位。
三、图解实现
KMP算法的关键点在于这种情况出现时该如何处理，如果是暴力搜索，这时候需要重置原串中的指针到第二个位置，再重新匹配，算法的复杂度是o(m*n)，而KMP算法可以优化暴力搜索，让原串中的指针只往后走，而不回来重复走。
我们观察到如果说字串中的指针向后走了，说明前面的位置是被匹配到了，我们可以设法利用前面已经在原串中匹配的字符，这样原串中的指针就只需要往后走，而不用往回走，将复杂度降到o(n)。
那么我们如何利用已经匹配过的字串呢？
在字串中，我们观察到，它的串中有重复的字符出现，所以才导致了可能需要从原串中回退，如果我们定义了一个数组记录好子串中每个字符对应的重复的位置在哪里，如下图所示：
这样的话，当我们发现，匹配到后面无法匹配时，我们需要让字串的指针回退到上一个位置的对应的重复的位置。
然后继续跟原串匹配，这里我们知道原来的字串位置之前的所有字符都被匹配了，所以需要找到与字串当前位置末尾的字符串相同的最长前缀字串，就可以接着匹配（这里不理解可以接着往后看）。
继续向后匹配
直到完成匹配，或者是找完原串没有匹配并返回。
看着流程很简单，也很容易理解，但是最难的地方在于next数组到底是什么？该如何实现呢？
首先，回答一下next数组是什么。
next数组实事上是字串的前缀字串与后缀字串的最长匹配长度，注意这里需要定义自身不是自身的匹配，因为如果自己是那么最长的匹配长度永远是自己的长度，那么再返回来匹配，还是要与现在指针指向的字符去匹配是没有意义的。也就是说这里的前后缀是指不包括尾（或首）字符的最大匹配长度，既最小长度需要为2，只有一个字符时的长度为0。
举几个例子方便理解
看这个例子可以很容易理解next数组的定义，所以上上面在遇到不匹配的字符，并且字串中有被匹配到的字符时，我们需要返回上一个字符的最大匹配处，再继续往后匹配。
所谓的前缀字串就是从第一个位置往后，不包括最后一个字符的所有字符串，后缀字串同理，这个从现在的用法来看就很容易理解啦！
我们现实现一下遍历，后面再讲解next数组的形成。
bool kmp(string str, string substr)
{
int* next = buildNext(substr);
int i = 0, j = 0;
while (i<str.length())
{
//字符被匹配时继续向后匹配
if (str[i] == substr[j])
{
i++;
j++;
}
//字串有被匹配时
else if (j > 0)
{
j = next[j - 1];
}
//字串没有被匹配时
else
{
i++;
}
if (j == substr.length())
{
break;
}
}
delete[] next;//这里是为了销毁动态数组
if (j == substr.length())
{
return true;
}
return false;
}
void call()
{
string str, substr;
cin >> str;
cin >> substr;
kmp(str, substr);
}
int main()
{
call();
return 0;
}
四、next数组的实现
next数组的实现是此算法的重点，我们前面已经看到了它实现的过程，如果让我们自己去写出这个数组是非常简单的，但是计算机如何实现呢？
我们可以定义一个变量来存储当前的最大匹配长度prefix_len，给它赋初值为0，这里需要回想一下，我们定义的前缀数组一定是从第一个字符开始的，所以说prefix_len 刚好可以记录当前匹配的字符数，也可以作为一个指针，非常契合后续遍历时的使用；
同样的next[0] 应该初始化为0；
定义一个位置指针从字符串的第二个字符开始，往后走，每走一下判断是否与prefix_len位置的指针所指向的字符匹配，有三种情况：
- 如果匹配，prefix_len +1，令next的值为prefix_len, 并且位置指针向后移一位；
- 如果不匹配，且prefix_len 为0， 说明没有匹配的字符，直接把位置指针后移即可；
- 难的是这种情况，不匹配但是prefix_len 不为0，说明之前有匹配项了，这时候可能会有匹配的情况出现，我们分析一下：
根据前两种情况，到这里时，prefix_len = 1,pos = 2， 接下来pos指针往后走；
现在发现，不匹配，且prefix_len不等于0，我们应该怎么办呢？有些
铁铁可能会说很简单，给prefix_len 赋0就可以，然后pos往后走，那么在这里确实是可以的，但是我们往后再看看；
来到这里之后再往后走；
现在还是不匹配，且prefix_len 不为0，若是把它赋为0，就不对了；
我们可以看到它应该是2，我们应该怎么办呢？
观察上图我们发现，其实目前pos的值与prefix_len-1，既它的前一个位置是有关的，与KMP的思想一样，因为prefix_len 不为0说明前面的prefix_len个字符是被匹配好的，我们可以利用它，看看更短的字串有没有匹配的，令prefix_len = next[prefix_len-1]，再去与当前的pos匹配。这样就很好的解决了问题。同时，也解决了想赋给0的情况。
代码实现如下：
#include<iostream>
#include <cstring>
using namespace std;
int* buildNext(string str)
{
int* next = new int[str.length()];
next[0] = 0;
int prefix_len = 0;
int i = 1;
while (i < str.length())
{
if (str[prefix_len] == str[i])
{
prefix_len++;
next[i] = prefix_len;
i++;
}
else
{
if (prefix_len == 0)
{
next[i] = 0;
i++;
}
else
{
prefix_len = next[prefix_len - 1];
}
}
}
/*for (int i = 0; i < str.length(); i++)
{
cout << next[i] << " ";
}
cout << endl;*/
return next;
}
//基础学习
bool kmp(string str, string substr)
{
int* next = buildNext(substr);
int i = 0, j = 0;
while (i<str.length())
{
if (str[i] == substr[j])
{
i++;
j++;
}
else if (j > 0)
{
j = next[j - 1];
}
else
{
i++;
}
if (j == substr.length())
{
cout << "true" << endl;
break;
}
}
delete[] next;
if (j == substr.length())
{
return true;
}
cout << "false" << endl;
return false;
}
void call()
{
string str, substr;
cin >> str;
cin >> substr;
kmp(str, substr);
}
int main()
{
call();
return 0;
}
那么你学会了吗？
总结
KMP算法是查找字串的一个优化算法，我个人在学习过程中感觉比较难理解的是next数组的迭代，没有看懂的铁铁可以找视频看看，再写写代码，这个代码是我自己写，可能有些冗余大家可以根据思想自己实现更好的代码。另外，欢迎大家在评论区讨论，一起学习。