JZTXT

KMP 代码模板

发布时间 2023-12-07 09:00:37作者: Chad-Wu

KMP 代码模板

由于我至今对原理依旧理解得不是很清楚，所以暂时忽略原理，直接上代码

首先KMP算法之所以效率高于Brute Force求解，是因为它能够使得文本串不用进行回溯，只要在模式串中进行操作。当进行一次匹配时，在任意字符失配时，我们便将比较的指针移动到对应的Fail Link Value上。因此第一步，我们需要求出模式串对应的Flink（或称next）数组。

简单来说，next数组的值就是比较当前字符之前子串中前缀和后缀相同的部分

void getFailLinkValue(int* next, string sub)
{
    int n = sub.size();
    int j = 0;
    next[j++] = -1; // 令第一个字符链接值为-1
    while (j < n) {
        int temp = next[j - 1];
        while (temp != -1 && s[temp] != s[j - 1]) temp = next[temp];/*这一步挺难理解的,当子串中匹配失败后，temp
    再次回退到它的next值中，有点类似于递归*/
        next[j] = temp + 1;
        j++;
    }
}

求出next数组，那么接下来就是简单的匹配了，唯一和暴力解法不同的就是回退的值不一样

int KMP_Match(string pat, string sub)
{
    int n = pat.size(), m = sub.size();
    int i = 0, j = 0;
    while (i < n) {
        if (j == -1 || pat[i] == sub[j]) {
            ++i; ++j;
        }
        else j = next[j];
        if (j == m) return i - m;//匹配成功
    }
    return -1; // Fail Match
}