当前位置：首页 > news >正文

写给自己的KMP——C++版本

news 来源：原创 2024/4/27 23:23:32

文章目录

一、前言
二、暴力搜索
三、KMP算法
四、关键点记录
五、总结

一、前言

又翻到了这个算法，一个常用的子串（子数组）匹配算法，看一遍学一遍，学一遍忘一遍，反反复复，不过每次回忆起来所用的时间越来少了，其本质上就是在暴力搜索的基础上加上 next 数组加速匹配，算法的关键在于 next 数组的理解和求解方法。

不想画图，缺少图解的算法很难给初学者讲清楚，所以本文也仅仅是个人的笔记而已，用于记录算法中关键点、帮助回忆或者理解其中的一些关键因素，如果想从头学习 KMP，还是去搜索其他资料吧，相关的内容有很多，有些文章写的很详细的。

今天的示例代码用C++来写，上一版的自己写的KMP我查了一下是C语言版本的，初看起来已经有点费劲了，随着时间的推移，我决定根据理解再写一次，写完才发现，和之前的风格判若两人。

二、暴力搜索

在原字符串中搜索模式串，最容易想到的就是暴力搜索，匹配则向后移动，不匹配则原串回溯，模式串归0，代码很容易实现，列举如下：

#include <iostream>
#include <string>
using namespace std;

int violence_find(string s, string p) {
    int m = s.size(), n = p.size(), i = 0, j = 0;

    while (i < m && j < n) {
        if (s[i] == p[j]) { // match character
            ++i;
            ++j;
        } else { // mismatch
            i -= j - 1;
            j = 0;
        }
    }

    return j == n ? i - j : -1;
}

int main() {
    string s("abdfdjfdkekfdaa5gsdsf");
    string p("fdkekfd");

    cout << violence_find(s, p) << endl;
    return 0;
}

典型的 O(MN) 解法，这种解法慢就慢在原字符串的回溯上，也就是语句 i -= j - 1; 的效果，当出现失配时，原字符串之前的匹配几乎“白费”，每次最多移动一个字符，而 KMP 算法决定利用之前的“努力成果”。

三、KMP算法

在 KMP 算法中先利用模式串构建一个 next 数组，当出现失配情况时根据模式串前缀和后缀情况，最大程序利用已经匹配的部分来达到加速查找的目的，只需要求一个 next 数组，其他部分和暴力匹配的代码很像：

int kmp_tmp(string s, string p) {
    int m = s.size(), n = p.size(), i = 0, j = 0;

    vector<int> next = std::move(gen_next(p));

    while (i < m && j < n) {
        if (s[i] == p[j]) {
            ++i;
            ++j;
        } else { // mismatch
            j = next[j];
            if (j == -1) {
                ++i;
                j = 0;
            }
        }
    }

    return j == n ? i - j : -1;
}

和暴力搜索的代码对照下，只有 else 中语句块不太一样，这个 i 只前进不后退了，其实这个里的 j == -1 语句可以合并到判定相等的 if 语句块中，完成 KMP 代码如下：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> gen_next(string p) {
    int n = p.size(), i = 0, j = -1;
    vector<int> next(n, -1);

    while (i < n - 1) {
        if (j == -1 || p[i] == p[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else j = next[j]; // mismatch, move j
    }

    return next;
}

int kmp(string s, string p) {
    int m = s.size(), n = p.size(), i = 0, j = 0;

    vector<int> next = std::move(gen_next(p));

    while (i < m && j < n) {
        if (j == -1 || s[i] == p[j]) {
            ++i;
            ++j;
        } else j = next[j]; // mismatch, move j
    }

    return j == n ? i - j : -1;
}

int main() {
    string s("abdfdjfdkekfdaa5gsdsf");
    string p("fdkekfd");

    cout << kmp(s, p) << endl;
    return 0;
}

四、关键点记录

next[i] 中记录的实际上是 p[0,i-1] 这个字符串中所有前缀和所有后缀交集中最长字符串的长度，比如'fdkekfd' 这个字符串所有前缀和所有后缀交集中最长字符串是 'fd'，其长度是2。
字符串的前缀和后缀不包括字符串本身。
next[0] 初始化成-1仅仅是一个编程技巧，你可以初始化成任意值，只要你分辨出是失配的情况即可，这里初始成 -1 正好可以和 s[i] == p[j] 这种情况合并，所以初始化成 -1 会常用一点。
在 KMP 算法中原串索引 i 比较傲娇，它只前进不会回溯，这也是 KMP 速度快的一个主要原因。
当出现失配时，模式子串的前缀和后缀有重合，可以直接移动模式串的前缀到刚刚匹配的后缀部分，但要记住如果没有重合的前缀和后缀，失配时移动模式串的速度会更快，这里容易弄反。