KMP算法理解,and优化(待发)

时间:2022-09-03 09:52:49

以前看kmp算法没有重视,如今发现当时的理解存在一些问题。 说kmp算法,先要说一般的匹配算法 一般匹配算法就是以keyword的首字母为标记。匹配过程遇到不匹配,标记移动到下一位,重新与文本串匹配。当keyword只有一个字母时,效率是一样的,但当keyword较长,极端情况是keyword自己本身没有重复字母,匹配过程中遇到文本子串与keyword最后一位不匹配时,我们自己心里清楚,完全没必要让标记只移动一位,可以整个移动keyword(length)-1位

char[] 0 1 2 3 4 5 6 7 ……
text a b c d e a a b ……
key a b c d e f

当然这种情况我们心里清楚,下一步完全可以直接比较key[0]和text[5]。


我们希望能将比较过的过程尽量不要重复,利用比较过的结果
当比较到 key[j]!= text[i] 时 说明key[0,j-1]==text[i-j,i-1]。
我们最希望的状态是 j直接回到0继续和text比较。
但当出现 key[0,,k]==key[(j-1)-k,j-1],时,且text[i]==key[k],我们必须从i,k处继续比较,以避免忽视这种匹配。

i i
text a b c a b c a b ……
key a b c a b a
j j
char[] 0 1 2 3 4 5

上表中k为2,
k就是key的子串key[0,j-1]中前后缀相等的最大长度。(因为数组下标从0开始,比较的是相等串的后一个字母,恰恰是key[k])。
abcaba为例

abcaba 0,j-1子串的前后缀 k
j=0
可以理解成j前面有几个元素
j-1=-1
这就是一些kmp算法设置next[0]=-1的原因
0
j=1 a 0
j=2 ab 0
j=3 abc 0
j=4 abca 1
j=5 abcab 2

kmp算法中next[j] 就是key[j]对应的k。next的值可以通过key[]的自我比较来确定,如果已知next[i]=k,即必有key[0,k]==key[i-k,i],则当key[i+1]=key[k+1]时,next[i+1]=k+1;否则找key[0,k]内的重复子串,此时可比较key[next[k]]==key[i+1] (相当于使用已知next[]搜索,跟kmp思想是一样的)。
于是就有kmp算法

//kmp主体,本代码只体现思想,并不考虑应用场景
int KMP(Str text,Str key,int next[])
{
    int i=0,j=0;
    while(i<text.length && j<key.length)
    {
        if(text.ch[i]==key.ch[j])
        {++i;++j;}
        else
        {
            j=next[j];
            if(j==0)++i;
        }
    }
    if(j>=key.length)
        return i-key.length;//若继续搜索可以把结果先存入数组
    else return -1;
}
//生成next数组
void getnext(Str key,int next[])
{
    int i=1,k=0;
    next[0]=0;//初始化
    next[1]=0;
    while(i<key.length)
    {
        if(key[i]==key[k])
        {
            next[++i]=++k;//next[i+1]=k+1
        }
        else
            k=next[k];//回溯对比key[next[k]]?=key[i]
    }

}