2021-05-24 从实现代码看KMP原理

KMP（时间复杂度O(m+n)）算法代码分两部分：

前置条件：假设主串长度为n,模式串长度为m,则m<=n。

优势：相比BF算法KMP算法不需回溯主串，可分块存储数据。

1. next数组获取（部分匹配表）。时间复杂度为O(m).

2.主串和模式串的匹配。时间复杂度为O(n).

// KMP next数组算法 

void getnext(lStr substr, int next[])

{

    int i = 1,j=0; // 假设串数组下标从1开始

    next[1]=0;

    while (i<substr.length)

    {

        if (j==0 || substr.ch[i]==substr.ch[j])

        {

            ++i;

            ++j;

            next[i]=j;

        }

        else

        {

            j=next[j];

        } 

    }

}

int KMP(lStr str, lStr substr, int next[])
{
    int i=1,j=1;//串从数组下标1位置开始存储
    while (i<=str.length && j<=substr.length)
    {
        if (j==0 || str.ch[i] == substr.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if (j>substr.length)
    {
        return i-substr.length;
    }
    else
    {
        return 0;
    }
}

关于next数组的🌰：

WX20210524-175433@2x.png

1. 初始化 i = 1, j = 0, next[1] = 0;
   2.while -> j=0 -> i=2, j =1, next[2] = 1;
   3.while->j!=0 && str[1] != str[2] -> else -> i = 2, j = 0;
   4.while->j=0 ->i=3, j=1, next[3] = 1;
   5.while->str[3] == str[1] -> i=4,j=2, next[4]=2;
   6.while->str[4] == str[2] -> i=5,j=3, next[5]=3;
   7.while->str[5] == str[3] -> i=6,j=4, next[6]=4;
   8.while->j!=0 && str[6]!=str[4]->else->i=6,j=2;
   9.while->j!=0 && str[6]!=str[2]->else->i=6,j=1;
   10.while->str[6] == str[1] -> i=7,j=2, next[7]=2;
   11.i>str.length 结束

关于KMP的改进方案：
由以上步骤8步骤9可见，kmp有无效回溯，改进方案在优化next数组求解部分。
nextval去除无效回溯，代码如下

void getnextval(lStr substr, int nextval[])
{
    int i=1, j=0;
    nextval[1] = 0;
    while (i<substr.length)
    {
        if (j==0 || substr.ch[i] == substr.ch[j])
        {
            ++i;
            ++j;
            if (substr.ch[i]!= substr.ch[j])
            {
                nextval[i] = j;
            }
            else
            {
                nextval[i] = nextval[j];
            }
            
        }
        else
        {
            j=nextval[j];
        }
        
    }
    
}

计算求解nextval:

WX20210524-184138@2x.png

以上为从代码看kmp全部内容，希望能有助理解，看文字真是不太容易理解:P