如何更好地理解KMP算法(C+Python)

2020-08-18   269 次阅读


请注意,本文编写于  340  天前,最后编辑于  234  天前,内容可能已经不具有时效性,请谨慎参考。

摘要:本文通过讲解next数组的生成以及如何使用next数组来实现KMP算法,采取C和Python进行编写。

正文:

关于KMP主要难点是next[]数组,模式串的下一个匹配位k及模式串向右移动的距离m,以下我分三步并结合例子讲解三个难点。

明确概念

  • ”前缀”和”后缀”:“前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。例如”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D].
  • 最大公共前后缀:基于前缀,和后缀概念,在一个字符串中,最长的相同的前缀和后缀称为最长公共前后缀,有的称之为最长首尾串。
  • Next[]数组:Next数组主要用来存放最大公共前后缀的长度值,此值定义为K值,即Next[]数组存储一组k值

举例:

字符串"A"的前缀和后缀都为空,共有元素的长度为0;
字符串"AB"的前缀为[A],后缀为[B],无共有元素,长度为0;
字符串"ABA"的前缀为[A, AB],后缀为[BA, A],共有元素"A",长度1;
字符串"ABAB"的前缀为[A, AB, ABA],后缀为[BAB, AB, B],共有元素"AB",长度为2;
字符串"ABABA"的前缀为[A, AB, ABA, ABAB],后缀为[BABA, ABA, BA, A],共有元素为"ABA",长度为3;
字符串"ABABAA"的前缀为[A, AB, ABA, ABAB, ABABA],后缀为[BABAA, ABAA, BAA, AA, A],共有元素为"A",长度为1;
综合以上,由字符串"A"、“AB”、“ABA”、“ABAB”、“ABABA”、“ABABAA"六个字符串组成的Next[]数组的值为:“001231”
即Next[]={0,0,1,2,3,1}

开始匹配

主串S和模式串T进行匹配时的起始位置:均为0

img

  • 模式串下一匹配位:定义为k,即下一次匹配时,主串i不变,模式串的新j值为j=k,即S[i]与T[k]进行比较。
  • K如何取值:k=next[j-1],为何用next[j-1]标识,之所以这样是为了更好的理解,j-1的含义是当j=5,i=10,T[5]!=S[10]时,需要取模式串”ABABAA”的next[]数组的第j-1=4位的数组值,此时Next[]={0,0,1,2,3,1}",在此next[]数组中,next[4]=3,即k=3。
  • 注:还可以用另一个方法计算k,模式串j前面(不包括j),即从位置0开始,到4(j-1=4)结束的字符串”ABABA”的最长公共前后缀为"ABA",它的长度值为3,即k=3,如下图:

img

  • 模式串T向右滑动的最大距离:定义为m,m=j-k(当j>0时,j为模式串的序号)

  • 字符串模式匹配时存在的两种情况:

    1.当模式串j=0时,即T[0]与主串Si且T[0]!=S[i]时,主串S位置加1,T向右滑动1位,此时j=0,T[0]将与主串Si继续比较。

    2.当模式串j>0时,即T[j]与主串Si且T[j]!=S[i]时,此时会用到KMP算法。

举例KMP算法

1.初始时,i =0,j=0;S[0]=”C”,T[0]=”A”,S[i]!=T[j],匹配失败,此时需要主串S位置加1,模式串T向右移动1位。

img

2.当 i =1,2,3,4时,均匹配失败;此时需要主串S位置加1,模式串T向右移动1位。

img

img

3.当i=5,6,7,8,9,j=0,1,2,3,4时,匹配成功,此时主串S位置加1,模式串T位置加1位。

img

4.当i=10,j=5时,匹配失败,S[10]=“F”, T[5]=“A”,S[10]!=T[5],见下:

img

5.在上图,i=10,j=5,接下来继续匹配时,需要主串中S[i]位置不变(i=10),模式串位置变为T[k],现在需要求k值。根据公式k=next[j-1],需要取模式串”ABABAA”的next[]数组的第j-1=5-1=4位的数组值,此时Next[]={0,0,1,2,3,1}",在此next[]数组中,next[4]=3,即k=3(j前面字符串”ABABA”的最长公共前后缀为"ABA",它的长度值为3,即k=3);此时,根据KMP算法,i=10不变,模式串T向右滑动m=j-k=5-3=2位,模式串新的j值为j=k=3,见下:

img

6.在上图,i=10,j=3,S[i]=S[10]=”F” ,T[j]=T[3]=”B”,S[10]!=T[3],接下来继续匹配时,需要主串中S[i]位置不变(i=10),模式串位置变为T[k],现在需要求k值。根据公式k=next[j-1],需要取模式串”ABABAA”的next[]数组的第j-1=3-1=2位的数组值,此时Next[]={0,0,1,2,3,1}",在此next[]数组中,next[2]=1,即k=1(j前面字符串”ABA”的最长公共前后缀为"A",它的长度值为1,即k=1);此时,根据KMP算法,i=10不变,模式串T向右滑动m=j-k=3-1=2位,模式串新的j值为j=k=1,见下:

img

依此类推:接下来,当i=12,13,14,15,16,j=1,2,3,4,5,匹配成功,模式串T在主串中的位置为11。

img

C语言版代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int length(char *str)	//这个函数是用来计算字符串的长度
{
    int cnt = 0;
    for(int i = 0;str[i]!='\0';++i)
        ++cnt;
    return cnt;
}

int *KMPnext(char *str)	//定义kmp算法的next数组生成函数
{
    int len = length(str);
    int *next = (int*)malloc(sizeof(int)*len);
    memset(next,0,sizeof(next));
    for(int j=1,k=0;j < len;++j)
    {
        while(k > 0 && str[j] != str[k])
            k = next[k-1];
        if(str[k] == str[j])
            ++k;
        next[j] = k;
    }
    return next;
}

int KMP(char *s,char *t,int *next)
{
    //s为主串,t为模式串
    int s_len = length(s);
    int t_len = length(t);
    for(int i = 0,j = 0; i <s_len;++i)
    {
        while(j > 0 && s[i] != t[j])
            j = next[j-1];
        if(s[i] == t[j])
            ++j;
        if(j==t_len)
            return i-j+1;
    }
    return -1;
}

int main()
{
    char s[30] = "CDFGFABABAFABABAAAQWEDC";
    char t[10] = "ABABAA";
    int local;
    int *next;
    next = KMPnext(t);  //将模式串传入函数求得next数组
    local = KMP(s,t,next);
    printf("%d\n",length(s));
    printf("next数组:");
    for(int i = 0;i<length(t);++i)
        printf(" %d",next[i]);
    printf("\n匹配的位置是:%d",local);
    return 0;
}

Python版代码

#python版KMP算法

def KMP_next(str: str)->[int]:          #定义next数组
    next = [0] * len(str)
    k = 0
    for j in range(1,len(str)):
        while k > 0 and str[j] != str[k]:
            k = next[k-1]
        if str[j] == str[k]:
            k+=1
        next[j] = k
    return next


def KMP(s : str, t : str,next : [int]) -> int:
    #s为主串,t为模式串,next为数组
    j = 0
    for i in range(0,len(s)):
        while j > 0 and s[i] != t[j]:
            j = next[j -1]
        if s[i] == t[j]:
            j = j+ 1
        if j == len(t):
            return i-j+1
    return -1

if __name__ == "__main__":

    s = "CDFGFABABAFABABAAAQWEDC"
    t = "ABABADA"
    next = KMP_next(t)
    print('NEXT数组:',next)
    ans = KMP(s,t,next)
    if ans != -1:
        print('匹配到模式串的位置为:',ans) 
    else:
        print('未匹配到模式串')

本文由 hongCYu 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
原文链接:https://hongcyu.cn/posts/kmp.html
最后更新于:2020-12-03 16:35:52

Coffee