KMP算法解决什么问题?举个例子

2020年2月26日19:51:59 发表评论 104 views

一、 KMP算法解决什么问题?

KMP解决的是用线性复杂度在主串中查找第一次出现模式串的下标。
如果使用普通方法,那就是用二重循环搜索,时间复杂度为 O(M*N)。M为主串长度,N为模式串长度。

【举例子】
使用KMP算法,我们可以用 O(N) 的时间复杂度在主串"abcdef@abga@cd"中查找模式串 “abga”。

二、理解KMP算需要理解哪些部分?

  1. 前缀、后缀概念
  2. next[N]数组
  3. next[N]数组的迭代求法
  4. 根据next[N]数组移动指向模式串的指针匹配主串

三、 拆分讲解

1. 前后缀概念、next[N]数组的意义

【举例子】
字符串str="babdefbab"的不同长度的前缀、后缀如表1.。

长度前缀后缀
1bb
2baab
3babbab
4babdfbab
5babdeefbab
6babdefdefbab
7babdefbbdefbab
8babdefbaabdefbab
9babdefbabbabcdefbab

其中相同长度的前缀和后缀相等的有b、bab、babdefbab。
相同长度的真前缀和真后缀相等的有b、bab。其中长度最长的相等真前后缀为bab。
【概念】
根据上面的例子我们可以抽象前缀、后缀的概念

  • 前缀指字符串的任意首部。 真前缀指不包含本身字符串的任意首部,字符串的真前缀长度要小于字符串的长度。
  • 后缀指字符串任意尾部。字符串的真后缀的长度要小于字符串的长度。
2. next[N]数组的意义

【概念】
next[i]表示str的下标为 0 到 i-1 的子串的最长的相等的真前后缀的长度。next[i]的范围为[-1,N-1]$。

【举例子】 仍然用字符串str="babdefbab"举例

i012345678
next[i]-100100012
3. next[N]数组的迭代求法
voidnextSolution(int*next,int len,char*pattern){int index=0,k=-1;
    next[0]=k;while(index<len-1){if(k==-1||pattern[index]==pattern[k]){
            next[++index]=++k;}else{
            k=next[k];}}}
  • 看图解释
    初始值 i=0,next[i]=0,k=next[i]
  1. k==-1时,next[i+1]=k+1。
    KMP算法解决什么问题?举个例子
  2. str[i]=str[k]时,next[i+1]=k+1。
    KMP算法解决什么问题?举个例子
  3. str[i] \ne str[k]时,迭代k=next[k]。
    KMP算法解决什么问题?举个例子
4. 根据next[N]数组移动指向模式串的指针匹配主串
intkmp(char* haystack,char* needle){constint len_ned=strlen(needle);if(len_ned==0)return0;constint len_hay=strlen(haystack);if(len_ned>len_hay)return-1;int next[len_ned];nextSolution(next,len_ned,needle);int index_hay=0,index_needle=0;while(index_hay<len_hay&&index_needle<len_ned){if(index_needle==-1||haystack[index_hay]==needle[index_needle]){
            index_hay++;
            index_needle++;}else{
            index_needle=next[index_needle];}if(index_needle==len_ned){return index_hay-len_ned;}return-1;}

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: