一、前言

本文使用C++来实现字符串子串匹配算法( KMP )。

说明:本文代码需支持C++标准编译器编译,以及可选单元测试工具googletest

项目地址:algorithm

二、函数声明

/* 生成 kmp 算法所需要的table */
std::vector<std::size_t> KmpTable(const char *substr) { }
/* 在字符串 str 中查找所有 substr 子串,并返回开始下标 */
std::vector<std::size_t> KmpSearch(const char* str, const char* substr) {}

三、函数实现

3.1 KmpTable

/* 复杂度 O(M) table 实例 请看单元测试       */
/* 1.判断substr[i] 是否与状态 k 相等        */
/* 1.1.相等substr[i+1] 则可以进入状态 k + 1 */
/* 1.2.否则查找状态 k 会回退到哪个状态        */
/* 2.将substr[i]的状态置为 k             */
std::vector<std::size_t> KmpTable(const char *substr) {
    std::vector<std::size_t> table(2, 0);
    std::size_t k = 0;

    for(std::size_t i = 1; substr[i] != '\0'; ++i) {
        while(k > 0 && substr[i] != substr[k]) {
            /* 返回状态 k */
            k = table[k];
        }
        /* 匹配进入状态 k + 1 否则进入状态 k */
        substr[i] == substr[k] ? ++k : k;
        table.push_back(k);
    }

    return table;
}

3.2 KmpSearch

/* 复杂度 O(N) */ 
std::vector<std::size_t> KmpSearch(const char* str, const char* substr) {
    assert(str != nullptr);
    assert(substr != nullptr);
    assert(substr[0] != '\0');

    std::vector<std::size_t> table = KmpTable(substr);
    std::vector<std::size_t> ret;
    std::size_t len = table.size() - 1;
    std::size_t k = 0;
    /* 与 kmpTable 思路相同 */
    for(std::size_t i = 0; str[i] != '\0'; ++i) {
        while(k > 0 && str[i] != substr[k]) {
            k = table[k];
        }
        str[i] == substr[k] ? ++k : k;
        if(k == len) {
            ret.push_back(i + 1 - len);
        }
    }

    return ret;
}

四、单元测试

TEST_F(KMPTest, KMPTable) {
    const char* str = "ACABACACD";
    std::vector<std::size_t> kase{0, 0, 0, 1, 0, 1, 2, 3, 2, 0};
    auto ans = KmpTable(str);
    ASSERT_EQ(ans.size(), kase.size());
    for(std::size_t i = 0; i < kase.size(); ++i) {
        ASSERT_EQ(kase[i], ans[i]);
    }
}

TEST_F(KMPTest, KMPSearch) {
    auto ret = KmpSearch("test", "t");
    ASSERT_EQ(ret.size(), 2);
    ASSERT_EQ(ret[0], 0);
    ASSERT_EQ(ret[1], 3);

    ret = KmpSearch("aaaa", "a");
    ASSERT_EQ(ret.size(), 4);
    for(std::size_t i = 0; i < 4; ++i) {
        ASSERT_EQ(ret[i], i);
    }
}
Last modification:May 12th, 2020 at 07:45 pm