算法实战：手把手教你用KMP算法解决字符串匹配问题

算法实战：手把手教你用KMP算法解决字符串匹配问题

引用

CSDN

1.

https://m.blog.csdn.net/2301_80402620/article/details/143250594

KMP算法是一种高效的字符串匹配算法，其核心思想是利用匹配失败之后的信息，尽量减少模式串与主串的匹配次数来达到快速匹配的目的。本文将详细介绍KMP算法的原理、实现及其与朴素字符串匹配算法的对比。

BMP算法简介

KMP算法是一种字符串匹配算法。核心思想是利用匹配失败之后的信息，尽量减少模式串与主串的匹配次数来达到快速匹配的目的。主要是一个next()函数的实现，该函数本身包含了匹配模式串的局部匹配信息即：部分字符串的最大前后缀相同的长度。KMP算法的时间复杂度是O（m+n）。

问题描述

有一个目标串str1，和一个模式串str2，现在要求模式串str2是否在目标串str1中以及出现的位置。

普通算法（朴素字符串匹配算法）

优点：

1. 简单易懂：朴素算法的实现简单直观，容易理解和编写。
2. 适用性广泛：适用于小规模字符串匹配，对于较短的字符串效果较好。
3. 不需要额外空间：朴素算法只需要常量级别的额外空间，空间复杂度低。

缺点：

1. 时间复杂度高：在最坏的情况下，朴素算法的时间复杂度为（O（（n-m+1）×m）），其中（n）是目标串长度，（m）是模式串长度。对于较长的字符串，效率较低。
2. 性能不稳定：当目标串和模式串长度差距较大时，朴素算法的性能会受到影响。
3. 无法利用已知信息：朴素算法每次只移动一个位置进行比较，无法利用已知信息来跳过一些不必要的比较。
4. 不适用于大规模数据：对于大规模数据集，朴素算法的效率明显不足，不适合用于实际生产环境。

#include <iostream>
#include <string>
// 朴素字符串匹配算法
int naiveSearch(const std::string &S, const std::string &P) {
    int n = S.length(); // 目标串长度
    int m = P.length(); // 模式串长度
    // 从目标串的第一个字符开始逐个检查子串
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // 逐个字符比较子串与模式串
        while (j < m && S[i + j] == P[j]) {
            j++;
        }
        // 如果找到完全匹配，返回起始位置
        if (j == m) {
            return i;
        }
    }
    // 未找到匹配，返回 -1
    return -1;
}
int main() {
    std::string S = "hello world";
    std::string P = "world";
    // 在目标串中搜索模式串
    int position = naiveSearch(S, P);
    if (position != -1) {
        std::cout << "模式串出现在位置: " << position << std::endl;
    } else {
        std::cout << "模式串未找到" << std::endl;
    }
    return 0;
}

KMP算法

算法优势：

1. 跳跃式匹配：BMP算法利用模式串中的信息，通过坏字符规则和好后缀规则来实现跳跃式匹配，可以在发现不匹配字符时快速移动模式串，从而减少比较次数，提高匹配效率。
2. 平均时间复杂度：BMP算法的平均时间复杂度为O（n+m），其中n为目标串长度，m为模式串长度。相比之下，朴素算法的平均时间复杂度为O（n*m），因此BMP算法在大部分情况下具有更高的匹配效率。
3. 适用性：BMP算法适用于大部分实际应用场景，尤其在处理长模式串和大文本串时表现优异。相比之下，朴素算法在处理大规模文本串时效率较低。

算法思想介绍：

首先讲解BMP算法的思路，以下图为示例：

依次向下对比，直到出现匹配不同的情况，如图：

在匹配中，可以知道主串匹配的前半部分的字符串（因为模式串已知，并且前部分已经匹配成功，通过模式串可以知道主串的字符。并且更重要的是，通过模式串，我们可以知道主串在已经匹配成功的部分具有的最大的前后缀字符串（后面会介绍为什么一定是最大的前后缀字符串）：

然后，因为匹配过程中已经出现匹配不成功，我们直接将将模式串向后平移当前模式串位置对应的前面部分的【最大前后缀字符串】的长度，如图：

然后紧接着继续匹配，若相同则继续主串下一位，不同则继续往后移动当前模式串位置对应的前面部分【最大前后缀字符串】的长度，知道匹配成功，或者匹配失败结束匹配，返回结果。

证明算法可行性：

为什么是移动长度为最大前后缀长度？并且为什么移动后继续匹配一定成立？

以下图为例进行证明：

在上图中，在出现匹配不成功时（箭头所指位置），假设模式串的最长前后缀（这里着重强调我们最初假设模式串和主串的最大前后缀只有“A”）为A，由匹配可知，在箭头之前是完全匹配的。

现假设在移动前缀到后缀位置的过程中遗漏了一种匹配（即存在一个A串可以满足移动要求）的情况，如下图所示 模式串2(模式串2 和 模式串 相同)

由模式串和模式串2以及主串之间匹配的关系可以看出来，根据三个字符串对应关系，可以推断相同部分字符串的字符。如图：

注意：根据三个字符串相同部分为A，然后先得到每一个列均为A，然后设第二个字符为B，则在匹配成功部分B列均为B，根据模式串2和模式串是相同的，可以推断出模式串前面的三个字符ABA。但是，问题出现：当前模式串的最大前后缀变成了“ABA”，而不是我们最初假设的“A”，产生矛盾，所以将模式串移动最大前后缀长度的情况下，不可能存在遗漏的可能。

警告：因此KMP算法现在转换为：假如当前匹配为第i位（主串）和第j位（模式串），当模式串和主串匹配成功时，两个同时往后移动一个单位（i++，j++），继续匹配；匹配不成功，将模式串往后移动当前字符对应的最大前后缀长度（假设为k）（则i不变，j = k）进行匹配，重新比较第i位和第j位；如果相同（i++，j++），不相同，再次移动最大前后缀长度（此时是k前面的最大前后缀，设长度为k1），然后i不变，j = k1；按照此思路，一直匹配，直到匹配结束。因此，算法现在需要知道当每一个字符串出现匹配不成功时对应移动的最大距离即：最大前后缀的长度，而这个最大前后缀的长度只与模式串有关系。并且，模式串的每一位出现匹配不成功均对应一个k，保证让模式串直接平移k个距离。我们将每一个模式串字符对应的k叫做next[]数组，这个数组是根据模式串构建的。即next[j] = k；

最大前后缀概念说明

注意：前缀永远是从字符串的第一位开始的

字符串->最大前后缀长度->最大前后缀字符串
a -> 0 -> 无
ab -> 0 -> 无
aba -> 1 -> a
ABAB -> 2 -> AB
ababc -> 0 -> 无

next[ ] 数组含义及构建

重要：next[]数组含义：每一个next[i] = k 对应模式串第i位字符之前部分的字符串（如图位置j之前的字符串）的最大相同前后缀长度k。如图：

若当前位置 j 与主串第i个位置的字符不匹配，则下一次比较的是模式串位置 K 与主串的当前位置i，这个 K 也就是 ;由于两个浅蓝色区域相同（因为next[j]的含义是j之前的长度为 j-1 的字符串的最大前后缀的长度，也就是最大前后缀的前缀的长度（前缀永远是从字符串的第一位开始的）。），因此 K 前面的区域肯定与主串相同，不需比较；如下图

next[j]

根据图片可以直观的看出来，移动之后， K前面的部分已经不需要比较了。

首先，给出next数组构建代码：

void GetNext(const string& str, vector<int>& next) {
    int j = -1, i = 0; // 初始化指针 j 和 i
    next[0] = -1; // 第一个位置的部分匹配值为 -1
    int length = str.length(); // 获取字符串长度
    while (i < length) {
        if (j == -1 || str[i] == str[j]) {
            next[i++] = next[j++];
        } else {
            j = next[j]; // 不匹配时，根据部分匹配值向前移动 j
        }
    }
}

开始讲解next[]数组的构建（假设模式串为 s）：

根据规定 ；接下来求其他的 ；

next[0] = -1
next[j]
对于 而言， 可得其必然为 （因为无论是否是最大前后缀，其将返回到第一个字符处进行匹配）。如图所示：当第二个元素不成功时，将返回第一个元素继续匹配。

next[1]
next[1] = 0

下面是一般情况的推导，即已知 next[j] 求 next[j + 1]，此处使用递推法进行推导：

如果next[j] = k，则如图：

由next[j]=k可以知道，k前面和j前面浅蓝色部分相同（最大相同前后缀部分）。现在分两种情况进行讨论：

1. s[k] = s[j]：如图所示

由图片可以看出，在当前这种情况下，对于j+1来说，能够找到k+1位置满足浅蓝色部分区域相同，因此当j+1和主串匹配不成功时，将移动最大前后缀长度后，比较的是k+1位和主串。因此：；

next[j + 1] = K + 1 = next[j] + 1
所以，综上所述，当s[k] == s[j] 时，那么next[j+1] = next[j] + 1 = k + 1；也就是next[j++] = k++；

2. s[k] ！= s[j]：

重要：这个情况非常复杂，也是next数组构建最难理解的部分!!

从next数组的定义出发：我们所要求的时当前位置之前有多长的前后缀相同。现在我们的问题是：已经知道第j位不同时该移动的距离，现在求的是第j+1位不同时该移动的距离。我们现在面临的情况是：

因此，在这种情况下，我们的目标是找到一个浅蓝色部分k1，使得出现下面这个图展示的情况：

如图所示，当第j位和第看k位不同时，前面有一个k1（目前k1未知，我们所要求的就是k1的位置）满足我们的要求，要想满足这种情况我们需要两个前提：1.使得浅蓝色部分的红色1处字符串和j之前的部分红色2处字符串相同，2.满足第k1位和第j位字符相同，

满足这两个条件后next[j+1] = k1即，当j+1不成功时模式串可以移动，然后比较k1处字符。

想要让字符串1和和字符串2直接相同是难以直接实现的，但是我们可以转换为另一个问题，如下图：

问题转换为：想找到字符串3和字符串1相同的部分，转换为字符串2和字符串1的部分；为什么？因为已知next[j] = k，即根据next数组定义，位置j前面部分字符串和位置k前面所有字符串是相同的即满足：

因此可以转换为字符串1和字符串2相同，这个等价关系是十分重要的。

那么如何得到k1使得字符串1和字符串2相同呢，根据next数组的定义next[j] = k，我们知道k前面的浅蓝色区域和 j 前面的浅蓝色区域相同，看上图，由于我们也知道next[k]（next[k]的含义就是k之前字符串所具有的移动相同最大后缀前的位置），为什么next[k]因已知？因为我们已经知道next[j]， 并且k < j， 因此我们可以得到 k1 = next[k];此时得到的k1满足字符串1和字符串3相同的要求;

我的理解：当j和k匹配不成功时，j前面一小块字符串3和k前面一小块字符串2是相同的，由于next[k] = k1，我们知道k前面一小块字符串2和k1前面从首字符到k1的字符串1是相同的，因此字符串1和字符串3是完全相同的。

因此就解决了 字符串1 和 字符串3 相等的问题，然后直接比较 K1 和 j ，若两者相同，则如图

因此：当k1和j相同时，由条件next[k] = k1， next[j] = k，next[j+1] = k1 + 1得到：;

next[j + 1] = K1 + 1 = next[K] + 1 = next[next[j]] + 1
但是如果k1和j不同呢？如图：

由图可以看出，此时情况和s[j] ！= s[k]情况相同，继续按照上面方法解决问题，可得结果：

next[j + 1] = next[K1] + 1 = next[next[K]] + 1 = next[next[next[j]]] + 1
若下一次 K2 依然和 j 不相等，那么又接着递归即可；一直到 Kn = 1，若此时 ，即当前元素和第一个元素不相同，则证明在 j + 1 前面没有相同的前缀和后缀，那么 。

s[j] != s[Kn]
next[j + 1] = 0
因此有代码：

if( j == -1 || str[i] == str[j] ) {
            next[i++] = j++;
        } else {
            j = next[j];
        }

KMP算法完整实现

#include <iostream>
#include <string>
#include <cstring>
#define WORD 50
#define MAXSIZE 100
using namespace std;
// 计算部分匹配值数组 next
void GetNext(char *str, int *next){
    int j = -1, i = 0;
    next[0] = -1;
    int length = strlen(str);
    while( i < length ) {
        if( j == -1 || str[i] == str[j] ) {
            next[i++] = j++;
        } else {
            j = next[j];
        }
    }
}  // GetNext
// KMP算法匹配
int KMP(char *str1, char *str2){
    int i = 0;   // 字符串匹配起始位置，可以修改
    int next[WORD];
    int length = strlen(str2);
    GetNext(str2, next); // 调用GetNext函数计算部分匹配值数组
    int j = 0;
    while(str1[i] != '\0' && j < length) {
        if( j == -1 || str1[i] == str2[j] ){
            i++, j++; // 匹配成功，继续比较下一个字符
        } else {
            j = next[j]; // 匹配失败，根据部分匹配值移动j
        }
        if( j == length) {
            return i - length; // 匹配成功，返回匹配位置
        }
    }
    return -1; // 未找到匹配，返回-1
}
int main(){
    char str1[MAXSIZE];
    char str2[MAXSIZE];
    cin >> str1; // 输入待匹配的字符串
    cin >> str2; // 输入模式串
    int result = KMP(str1, str2); // 调用KMP算法进行匹配
    if (result > -1) {
        cout << "匹配结果为：" << result; // 输出匹配结果
    } else {
        cout << "未找到！！！" << endl; // 输出未找到匹配
    }
    return 0;
}