KMP算法

引子

假设我们解决这样一个问题：

有字符串S与模式串P，想知道模式串P在字符串S的什么位置，应如何解决？

解决子串匹配问题
字符串S：“abcabcabd”
模式串P：“abcabd”

采用暴力(Brute Force)算法，即朴素算法的做法：
依次比较每个字符，直到串的每个字符都一一吻合。
算法执行流程：

1. 每个字符比较后，直到发现c与d不符合，将模式串向后移动。
   

2. 发现b与a不符合，模式串再向后移动。
   

3. 发现c与a不符合，模式串再向后移动。
   

4. 每个字符比较，发现一一吻合。

朴素算法中，一旦匹配不成功，要到目标串下一位，再和模式串从头匹配，流程相对繁琐。很明显，例子中的2与3步骤是可以省略的，关键在于，能否保存两个串中，相同部分的字符，每次移动模式串时，直接忽略其中字符不相同的部分，来优化整个匹配流程。这就是KMP算法的核心。

什么是KMP算法

KMP算法，即Knuth-Morris-Pratt 字符串查找算法。KMP算法由Knuth、Morris和Pratt提出，是字符串匹配算法的一种改进算法。

KMP算法通常需要一个部分匹配表（Partial Match Table）。用next数组保存部分匹配值，也就是前 i 个字符所组成的子串的真前缀与真后缀相同的最大长度。当发生不匹配时，直接从next数组保存的索引开始匹配，忽略不必要的匹配操作。

需要知道的知识

真前缀

真前缀，指字符串首部开始的除了最后一个字符的所有子串。
例如"abcde"的真前缀有[a,ab,abc,abcd]

真后缀

真后缀，指字符串尾部开始的除了第一个字符的所有子串。
例如"abcde"的真后缀有[bcde,cde,de,e]

真前缀与真后缀相同的最大长度

例如"ababa"的真前缀为[a,ab,aba,abab]，真后缀为[baba,aba,ba,a]，其中相同的最长子串为"aba" 即最大长度为3。

next数组

根据模式串中每个字符的，前 i 个字符所组成的子串的真前缀与真后缀相等的最大长度，可求的一个next数组。
以"abcabd"为例：

当目标串与模式串不匹配时，模式串向右移动位数 = 已经匹配的字符数 - 前一位已匹配字符的最大长度值。

实际操作中，会用指针的移动来代替模式串的移动，也就是将比较指针，移动到前一位已匹配的next数组值的索引。

字符串S：“abcabcabd”
模式串P：“abcabd”
例子中，在模式串索引为5的字符d出现问题，会将比较指针移动到next数组索引为4的值，也就是从模式串中索引为2的字符开始下轮比较。

注意：不同的写法会有不同的next数组，尽管写法不同，但整体的算法思想是相同的，区别只在于如何利用next数组。

例如同样的模式串的不同next数组：

其中-1通常会在算法中作为边界值使用。

当目标串与模式串不匹配时，模式串向右移动位数 = 不匹配的字符索引 - 不匹配字符的所对应的next数组值。

两种方式中，“已经匹配的字符数” 在 “不匹配的字符索引” 的前一位。“前一位已匹配字符的最大长度值” 同样在 “不匹配字符的所对应的next数组值” 的前一位。也就是说两个不同next数组在比较中，使得模式串移动的位数是一样的，所达到的实际效果也是一样的。

KMP算法为什么是正确的

KMP算法是如何正确的

前面已经做了很多铺垫。当发生字符不匹配时，实际上是将模式串中已经匹配部分的后缀与模式串的前缀进行比较，获取两者相同的部分，进而忽略不匹配的部分。由于发生部分不匹配时，在不匹配之前的字符一定是匹配的，所以这些步骤在模式串本身就可以实现。得到next数组的过程，实际上就是模式串自己匹配自己的过程，也就是获取模式串本身的真前缀和真后缀相同的最大长度，将长度保存下来，即得到要获取的next数组。匹配的时候，模式串再根据next数组的值进行移动。

next数组的实现

next数组的实现通常分为：
初始化，前后缀不相同时操作，前后缀相同时操作，next数组赋值。

• 初始化包括指针 i 和指针 j 的值，还有next数组的索引为 0 的值。
• i 为标准指针， j 为比较指针。在以 i 为标准在for循环中，遍历每个字符，在内嵌的while循环中比较字符是否相同，如果不相同便将已经匹配的字符数传给比较指针 j 。
• 在之前以 i 为标准的for循环中，如果比较字符相同，使比较指针 j 自增， j 不仅代表比较指针，同时也记录已匹配的字符数。
• 最后将已匹配的字符数记录到next数组。

各类写法代码模板

下标0开始算法常用模板

void get_next(string p,int next[])
{
int j = 0;
next[0] = 0;
for(int i = 1; i < p.size(); ++i)
{
while (j > 0 && p[i] != p[j]) {
j = next[j - 1];
}
if (p[i] == p[j]) {
++j;
}
next[i] = j;
}
}

int match(string haystack, string needle)
{
int next[needle.size()];
get_next(needle,next);
int j = 0;
for (int i = 0; i < haystack.size(); ++i)
{
while(j > 0 && haystack[i] != needle[j])
{
j = next[j - 1];
}
if (haystack[i] == needle[j])
{
++j;
}
if (j == needle.size() ) {
return (i - needle.size() + 1);
}
}
return -1;
}

下标1开始算法常用模板

// 注意：模板是手动输入cin>>char[N]+1，从数组下标为1开始输入，并且是从下标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 = next[j];
if (p[i] == p[j + 1]) ++j;
next[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; ++i)
{
while (j && s[i] != p[j + 1]) j = next[j];
if (s[i] == p[j + 1]) ++j;
if (j == m)
{
j = next[j];
// 匹配成功执行逻辑
}
}

KMP优化算法

void get_nextVal(string p, int next[])
{
int i = 0; int j = -1;
next[0] = -1;
while (i < p.size())
{
if (j == -1 || p[i] == p[j])
{
++i; ++j;
next[i] = (p[i] != p[j] ? j : next[j]);
}
else
j = next[j];
}
}

int match(string s, string p)
{
int i = 0; int j = 0;
while (i < s.size() && j < p.size())
if (j == -1 || s[i] == p[j])
{
++i; ++j;
}
else
j = next[j];
if (j == p.size())
return i - j;
else
return -1;
}

最后

以上就是幸福机器猫为你收集整理的字符串匹配KMP算法讲解KMP算法引子什么是KMP算法KMP算法为什么是正确的各类写法代码模板的全部内容，希望文章能够帮你解决字符串匹配KMP算法讲解KMP算法引子什么是KMP算法KMP算法为什么是正确的各类写法代码模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。