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

一、 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.。

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

• 前缀指字符串的任意首部。 真前缀指不包含本身字符串的任意首部，字符串的真前缀长度要小于字符串的长度。
• 后缀指字符串任意尾部。字符串的真后缀的长度要小于字符串的长度。

2. $next[N]$数组的意义

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

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

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。
   
2. 当$str[i]=str[k]$时，next[i+1]=k+1。
   
3. 当str[i] \ne str[k]str[i]​=str[k]时,迭代k=next[k]。
   

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;}