KMP算法中next数组求解理解

KMP算法中next数组求解理解

next数组定义

对于模式串中当前位置j，next[j]表示此之前的字符串中最长相同前缀后缀长度。

next数组求解

void GetNext(char* str, int* next)
{
    int length = strlen(str);
    next[0] = -1;
    int k = -1;
    int j = 0;

    while (j < length - 1)
    {
        if (k == -1 || str[j] == str[k])
        {
            ++k;
            ++j;
            next[j] = next[k] + 1;
        }
        else
            k = next[k];
    }
}

个人理解

整体过程是顺序求解，利用过去的结果计算现在的结果，动态规划的思想。k就意味着在j位置是最长前缀后缀字符串之外需要比较的第一个字母(注意字符串起始位置从0开始)。

对于next[j]的结果有两个分支，若str[j] == str[k]则长度加1，比较容易理解；若str[j] != str[k]的情况下，为何k = next[k]? 假设此时已经有k长度的前缀后缀字符串，但str[j] != str[k]，k = next[k]意味着前缀中最长前缀后缀字符串之外需要比较的第一个字母(也是长度值)。由于之前k长度的前缀后缀是相同的字符串，所以此时对前缀所找出的次最长前缀后缀字符串必然等于后缀的次最长前缀后缀字符串，但此时需要比较的字符就变为str[j] = str[next[k]]了。即此时需要比较的为0,1,...,k和j-k,j-k+1,...,j两个字符串，并且其中0,1,...,k-1已经比较过了(过去的结果)，所以比较k和j位置的字符即可。