讨论KMP.3 match[j] 的另一种定义

陈越发表于2022年12月15日

如果将 match[j] 定义为 pattern[0...j] 首尾匹配子串的最大长度，该如何修改 KMP 和 BuildMatch 的实现？

89 回复

1楼

君子立命-一生无悔发表于2023年05月21日

要让 KMP 函数返回模式在文本中的子串，可以修改函数的返回类型为字符串类型。同时，在 KMP 函数内部要记录子串在文本中的起始和终止下标，然后返回这个子串。下面是一个简单的修改版本： #include <iostream>#include <cstring>using namespace std; string KMP(string text, string pattern){    int tlen = text.size();    int plen = pattern.size();    int fail[plen + 1];    memset(fail, -1, sizeof(fail));     for (int j = 1; j < plen; ++j) {        int i = fail[j - 1];        while (pattern[j] != pattern[i + 1] && i >= 0) i = fail[i];        if (pattern[j] == pattern[i + 1]) fail[j] = i + 1;    }     int i = 0, j = 0;    while (i < tlen && j < plen) {        if (text[i] == pattern[j]) {            ++i; ++j;        } else if (j == 0) {            ++i;        } else {            j = fail[j - 1] + 1;        }    }     if (j == plen) {        return text.substr(i - plen, plen);    } else {        return "not found";    }} int main(){    string text = "ABCABCABCABD";    string pattern = "ABCABD";    cout << KMP(text, pattern) << endl; // output: ABCABD    return 0;} 在 main 函数里，我们用 cout 输出 KMP 函数返回的字符串。这样，就可以在调用 KMP 函数后方便地输出子串了。 riqilang wu如果将 match[j] 定义为 pattern[0...j] 首尾匹配子串的最大长度，该如何修改 KMP 和 BuildMatch 的实现？如果将 match[j] 定义为 pattern[0...j] 首尾匹配子串的最大长度，可以按照以下步骤完成 KMP 函数和 BuildMatch 函数的实现： 在 KMP 函数中，对于所有 j < plen， match[j] 的值就是 fail[j] 的值加一（由于 fail 数组存储的是最后一个字符的最长公共前后缀长度，因此需要加一）。 BuildMatch 函数的实现也要相应地改变。在计算 fail 数组的过程中，可以顺便求出 match 数组的元素值。具体来说，只需要在 if (pattern[j] == pattern[i + 1]) 的分支中添加 match[j] = match[i] + 1; 的语句即可。 下面是 KMP 函数和 BuildMatch 函数的修改版本： void BuildMatch(string pattern, int* fail, int* match){    int plen = pattern.size();    fail[0] = -1;    match[0] = -1;     for (int j = 1; j < plen; ++j) {        int i = fail[j - 1];        while (pattern[j] != pattern[i + 1] && i >= 0) i = fail[i];        if (pattern[j] == pattern[i + 1]) {            fail[j] = i + 1;            match[j] = match[i] + 1;        } else {            fail[j] = -1;            match[j] = -1;        }    }} int KMP(string text, string pattern){    int tlen = text.size();    int plen = pattern.size();    int fail[plen], match[plen];    memset(fail, -1, sizeof(fail));    memset(match, -1, sizeof(match));     BuildMatch(pattern, fail, match);     int i = 0, j = 0;    while (i < tlen && j < plen) {        if (text[i] == pattern[j]) {            ++i; ++j;        } else if (j == 0) {            ++i;        } else {            j = fail[j - 1] + 1;        }    }     if (j == plen) {        return match[j - 1];    } else {        return -1;    }} 在 KMP 函数中，我们新增了一个 match 数组来存储首尾匹配子串的最大长度。BuildMatch 函数在计算 fail 数组的同时，顺便计算 match 数组的元素值。在调用 KMP 函数时，我们得到的匹配结果就是首尾匹配子串的最大长度，如果匹配失败则返回 -1。

君子立命-一生无悔发表于2023年05月21日

讨论KMP.3 match[j] 的另一种定义

友情链接

关注我们

关于我们