KMP字符串匹配算法之C++实现

简述

如标题所言，KMP 是一种字符串匹配算法，我也是偶然了解到的。

关于这个算法更详细的内容请参考阮一峰的博文：字符串匹配的KMP算法

要说字符串匹配，在不知道什么算法的情况下，很容易想到写一个两层循环来遍历，思路很简单，也很容易实现，不过效率却不怎么样。

很巧的是，这个题我真就在一次笔试还是面试中遇到了，当时我隐约记得有一个字符串匹配算法之前有看过，但又想不起来，最后还是无赖两层循环暴力解……

所以现在来重新好好理一理这个 KMP 算法~

C++实现

关于算法的内容此处不赘述了，建议阅读阮一峰大大的博文，讲的非常清楚！

在我的实现中，我将整个 KMP 算法分为了两部分，一部分是生成要匹配的子串的部分匹配表，另一部分则是根据部分匹配表进行匹配。

同时我将所有匹配到的位置用一个 vector<int> 类型的数组保存并返回。如果只需要匹配第一个即可，那么可以在匹配到一个字串之后就跳出循环并返回结果。

// 对KMP算法的C++实现
// KMP算法：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

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

// 获取字符串的部分匹配表
unique_ptr<int[]> GenPartialMatchTable(string& str) {
    size_t len = str.length();
    unique_ptr<int[]> table(new int[len]);  // 申请动态数组，元素未定义
    size_t i, j;
    for (i = 0; i < len; i++) {
        table[i] = 0;  // 初始化动态数组的元素
        for (j = 1; j <= i; j++) {
            if (str.substr(0, j) == str.substr(i - j + 1, j)) {
                table[i] = j;  // 更新部分匹配值使其取较大值
            }
        }
    }
    return table;
}

// 查找字符串匹配的位置
vector<int> kmp(string& str, string& sstr) {
    vector<int> vec;  // 返回所有匹配到的子串的位置
    unique_ptr<int[]> table = GenPartialMatchTable(str);  // 函数结束后自动销毁。移动构造函数，接管源对象
    size_t i = 0, j = 0;
    for (i; i < sstr.length(); i++) {
        for (j; j < str.length(); j++) {
            if (sstr[i + j] != str[j]) {
                if (j != 0) {
                    int step = j - table[j - 1];  // 移动位数 = 已匹配的字符数 - 对应的部分匹配值
                    i += step - 1;  // 移动j位，外循环还会+1
                    j = table[j - 1];
                }
                break;
            }
        }
        // 当且仅当字符串完全匹配后 j 与要匹配的字符串的长度相等
        if (j == str.length()) {
            vec.push_back(i);
            j = 0;  // 重新初始化为0
        }
    }
    return vec;
}

int main() {
    string str = "ABCDABD";  // 要匹配的子串
    string sstr = "BBC ABCDAB ABCDABDABDE";  // 用于匹配子串的字符串
    vector<int> vec = kmp(str, sstr);
    for (size_t i = 0; i < vec.size(); i++) {
        cout << vec[i] << endl;
    }
    return 0;
}