C++ kmp算法模板代码解读("C++ KMP算法模板代码详细解读与实战应用")

原创

ithorizon 6个月前 (10-20) 阅读数 24 #后端开发

C++ KMP算法模板代码详细解读与实战应用

一、KMP算法简介

在字符串匹配算法中，KMP（Knuth-Morris-Pratt）算法是一种高效的模式匹配算法。KMP算法的核心思想是当出现不匹配时，能够利用已经匹配的信息，将模式串尽大概多地向右移动，从而避免从头起始匹配，节约搜索高效。

二、KMP算法的基本步骤

KMP算法核心分为两个步骤：计算部分匹配表（Next数组）和搜索过程。

2.1 计算部分匹配表（Next数组）

部分匹配表（Next数组）记录了模式串中每个位置之前的子串的最长相同前后缀的长度。计算Next数组的目的是为了在不匹配时，能够知道模式串应该向右移动多少位。

2.2 搜索过程

搜索过程利用Next数组，当出现不匹配时，选择Next数组中的值，将模式串向右移动相应的位数，继续进行匹配。

三、C++ KMP算法模板代码解读

以下是一个C++ KMP算法的模板代码，我们将逐步进行解读。


#include 
#include 
#include 
using namespace std;
// 计算Next数组
void getNext(const string& pattern, vector& next) {
    int j = 0;
    next[0] = -1;
    for (int i = 1; i < pattern.size(); i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1] + 1;
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
}
// KMP搜索算法
int KMP(const string& text, const string& pattern) {
    vector next(pattern.size());
    getNext(pattern, next);
    int i = 0, j = 0;
    while (i < text.size() && j < pattern.size()) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == pattern.size()) {
        return i - j; // 匹配圆满，返回匹配起始位置
    }
    return -1; // 匹配挫败，返回-1
}
int main() {
    string text = "ABCDABD";
    string pattern = "ABD";
    int pos = KMP(text, pattern);
    if (pos != -1) {
        cout << "匹配圆满，起始位置：" << pos << endl;
    } else {
        cout << "匹配挫败" << endl;
    }
    return 0;
}

3.1 getNext函数解析

getNext函数用于计算模式串的Next数组。以下是函数的具体解析：


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

函数中，我们初始化j为0，并将next数组的第一个元素设置为-1。接下来，我们遍历模式串，对于每个字符，我们尝试找到它的最长相同前后缀。如果当前字符与模式串中j位置的字符不匹配，我们会选择next数组回溯到上一个位置，直到找到匹配的字符或者j为0。如果找到匹配的字符，我们将j向前移动一位。最后，我们将j的值赋给next数组的当前位置。

3.2 KMP函数解析

KMP函数是KMP算法的核心部分，用于在主串中搜索模式串。以下是函数的具体解析：


int KMP(const string& text, const string& pattern) {
    vector next(pattern.size());
    getNext(pattern, next);
    int i = 0, j = 0;
    while (i < text.size() && j < pattern.size()) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == pattern.size()) {
        return i - j; // 匹配圆满，返回匹配起始位置
    }
    return -1; // 匹配挫败，返回-1
}

函数首先调用getNext函数计算模式串的Next数组。然后，我们使用两个指针i和j分别指向主串和模式串的当前位置。在搜索过程中，如果当前字符匹配或者j为-1（即模式串的最长相同前后缀为0），我们将两个指针同时向前移动。如果当前字符不匹配，我们会选择Next数组回溯模式串的指针j。如果模式串的指针j移动到模式串的末尾，说明匹配圆满，返回匹配的起始位置。否则，如果遍历完主串仍然没有找到匹配，返回-1即匹配挫败。

四、KMP算法的实战应用

下面我们通过一个实例来演示KMP算法的实战应用。

4.1 实例：在主串中查找模式串

假设我们有以下主串和模式串：


string text = "ABCDABD";
string pattern = "ABD";

我们使用KMP算法查找模式串在主串中的位置。以下是执行KMP算法的代码：


int main() {
    string text = "ABCDABD";
    string pattern = "ABD";
    int pos = KMP(text, pattern);
    if (pos != -1) {
        cout << "匹配圆满，起始位置：" << pos << endl;
    } else {
        cout << "匹配挫败" << endl;
    }
    return 0;
}

执行上述代码，我们会得到以下输出：

匹配圆满，起始位置：2

这即模式串“ABD”在主串“ABCDABD”中的起始位置为2。