c++ 实现KMP算法

使用C++实现KMP算法

KMP算法，全称为Knuth-Morris-Pratt算法，是一种快速匹配字符串的算法，常用于查找一个字符串在另一个字符串中的出现位置。本文将详细讲解如何使用C++实现KMP算法。

KMP算法的思路

KMP算法的核心思想是在匹配字符串时，尽可能减少比较的次数，从而提高匹配效率。具体来说，KMP算法利用匹配字符串中前缀和后缀的相似性，在匹配时通过一个模式串的“状态机”指引从而大幅减少比较的次数。

下面是KMP算法的主要流程：

1. 初始化，设置两个指针i,j指向模式串p的第一个字符；
2. 从左向右依次比较主串s中的每个字符和p中的对应字符；
3. 当模式串p中第j个字符与主串s中的第i个字符相等时，则i,j同时后移；
4. 当模式串p中第j个字符与主串s中的第i个字符不相等时，需要根据p中已匹配部分的“前缀”和“后缀”来决定下一步匹配的位置，具体而言：①当j==0时，i向右移动一位；②当j!=0时，j跳到p的前j-1个字符组成的子串中最长的“前缀”和“后缀”相等的位置的下一个位置，即j=next[j-1]；
5. 当模式串p中所有字符均已匹配，则匹配成功，返回i-p的长度，即主串中匹配到的开始位置；
6. 当主串s中所有字符均已匹配完还没有匹配成功，则匹配失败，返回-1。

其中，next数组是KMP算法的关键。next数组记录的是针对每个字符，其之前的字符中最大前后缀匹配长度的值，它决定了在匹配过程中，模式串p中已匹配部分所形成的“状态机”从哪个位置开始继续匹配。next数组可通过类似动态规划的方式进行预处理。

C++实现

在C++中实现KMP算法，我们需要定义一个函数KMP(const char s, const char p)，其中s是主串，p是模式串。KMP函数返回的是模式串在主串中匹配到的开始位置。下面是完整代码：

#include <iostream>
#include <cstring>

using namespace std;

void getNext(const char* p, int* next) {
    int i = 0;
    next[0] = 0;
    for (int j = 1; j < strlen(p); j++) { // 遍历模式串p
        while (i > 0 && p[i] != p[j]) {
            i = next[i - 1];
        }
        if (p[i] == p[j]) {
            i++;
        }
        next[j] = i;
    }
}

int KMP(const char* s, const char* p) {
    int i = 0, j = 0;
    int next[strlen(p)];
    getNext(p, next);
    while (i < strlen(s) && j < strlen(p)) {
        if (j == 0 || s[i] == p[j]) {
            i++;
            j++;
        }
        else {
            j = next[j - 1];
        }
    }
    if (j == strlen(p)) {
        return i - j;
    }
    else {
        return -1;
    }
}

int main() {
    const char* s = "ABCABE";
    const char* p = "ABE";
    int pos = KMP(s, p);
    if (pos != -1) {
        cout << "在主串中匹配到模式串的位置为：" << pos << endl;
    }
    else {
        cout << "匹配失败！" << endl;
    }
    return 0;
}

上面代码中的getNext函数用于预处理next数组，KMP函数用于匹配字符串，其实现方式即上文所述的KMP算法流程。

下面是两个实例说明，其中s是主串，p是模式串，pos表示p在s中的开始匹配位置：

• s = "ABCABE", p = "ABE" => pos = 3
• s = "AABAAAB", p = "AAA" => pos = 2

总结

本文详细讲解了如何使用C++实现KMP算法。在KMP算法的实现过程中，需要定义KMP函数和getNext函数，需要注意每个函数的作用和实现细节。在实际使用KMP算法时，我们只需要调用KMP函数即可。