Java教程

对kmp算法的理解与应用

本文主要是介绍对kmp算法的理解与应用,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

近日刷题是遇到了kmp算法,再进一步在b站上找网课学习之后,对此有了更深一步理解

对于长度为 mm 的字符串 ss,其前缀函数 \pi(i)(0 \leq i < m)π(i)(0≤i<m) 表示 ss 的子串 s[0:i]s[0:i] 的最长的相等的真前缀与真后缀的长度。特别地,如果不存在符合条件的前后缀,那么 \pi(i) = 0π(i)=0。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。

我们举个例子说明:字符串 aabaaabaabaaab 的前缀函数值依次为 0,1,0,1,2,2,30,1,0,1,2,2,3。

\pi(0) = 0π(0)=0,因为 aa 没有真前缀和真后缀,根据规定为 00(可以发现对于任意字符串 \pi(0)=0π(0)=0 必定成立);

\pi(1) = 1π(1)=1,因为 aaaa 最长的一对相等的真前后缀为 aa,长度为 11;

\pi(2) = 0π(2)=0,因为 aabaab 没有对应真前缀和真后缀,根据规定为 00;

\pi(3) = 1π(3)=1,因为 aabaaaba 最长的一对相等的真前后缀为 aa,长度为 11;

\pi(4) = 2π(4)=2,因为 aabaaaabaa 最长的一对相等的真前后缀为 aaaa,长度为 22;

\pi(5) = 2π(5)=2,因为 aabaaaaabaaa 最长的一对相等的真前后缀为 aaaa,长度为 22;

\pi(6) = 3π(6)=3,因为 aabaaabaabaaab 最长的一对相等的真前后缀为 aabaab,长度为 33。

有了前缀函数,我们就可以快速地计算出模式串在主串中的每一次出现

 

 

 这里借用力扣某位大佬的图解释下

我们可以先看看如果不使用 KMP,会如何进行匹配(不使用 substring 函数的情况下)。

首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。

首次匹配的「发起点」是第一个字符 a。显然,后面的 abeab 都是匹配的,两个指针会同时往右移动(黑标)。

在都能匹配上 abeab 的部分,「朴素匹配」和「KMP」并无不同

作者:AC_OIer
链接:https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
来源:力扣(LeetCode)

而kmp算法之所以能够简化运算的原因,就在于其next数组,next数组帮助你跳过了很多不正确的选项,使运算更加简单,下面我们用一行简单的代码来求解next数组

void getvoid GetNext(int next[],int length,char *s){

 
void GetNext(char*s,int length,int next[]) {     next[0]=0;     int i=1,j=0;
//首先我们初始化j等于零,其中,j表示的是模式串前缀的最后一个数的下标志,同时也表示前后缀相同的最大值,j表好似的是后缀的最后一个下标所指的位置
    for(i=1;i<length;i++){         while(j>0 && s[i]!=s[j]){             j=next[j-1];      //当其不相等的时候,用while循环回溯         }         if(s[i]==s[j])       //相等的时候j向前加         {             j++;         }         next[i]=j;        //更新next数组,,主义,这里使用next[i]=j     } }      int strStr(char* haystack, char* needle) {     int numssize1=strlen(haystack);     int numssize2=strlen(needle);//先得到模式串和目标川的长度          if(numssize2==0){         return 0;//若模式串的长度为零,返回零,符合c语言中的定义???     }     int next[numssize2];     int j=0,i=0;     GetNext(needle,numssize2, next);//初始化next数组     for(i=0;i<numssize1;i++)     {         while(j>0 && haystack[i]!=needle[j]){   //此时的i和j和上文的i,j表示的意思不同,初学者常犯的错误(当然也包括我)             j=next[j-1];                                  //若匹配不成功 则回溯,正是在这一步简化了运算,为何,因为既然数组下标能够加到j,说明其前面的几个数必然已经和目标串的前j个字符                                                               //匹配成功了,那么这时i不动,我们只需要在比较第needle[next[j-1]+1]和haystack[i]即可,换句话说,                                                               //此时重置了匹配进程,haystack中只有前next[j-1]个数被用到了,而不是向之前一样j个都被用到了,                                                              //相反,此时若匹配失败的话,将会因为while循环不断回溯,一直到0时,将会(注意此时,j任然指向needle)         }         if(haystack[i]==needle[j]){             j++;                                         //此时如匹配成功,j++         }         if(j==numssize2)                      //说明历经考研之后,j成功来到了了末尾,注意!此时j在最后一次时为j-1,相等后+1,即此时next[j]已经越界了,知识我们没有使用而已,此后如要         return (i-numssize2+1);              //重新使用的话,还是得小心                                                           //此时i已经指到对应位置+numssize的地方,又根据题意要求,我们加上1     }     return -1;                                   //若经历了所有遍历后,函数没有在上一个出口返回,说明没有目标川中没有与模式串匹配的地方,那么,返回-1 }
想说的,该注意的点都已经,写在注释里,希望能对大家有所帮助!!!

 

  

这篇关于对kmp算法的理解与应用的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!