超详细超全超好理解的KMP算法

定义

KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。

先看这个视频，再看下边的代码实现：

【油管阿三哥讲KMP查找算法，中英文字幕，人工翻译，简单易懂】 https://www.bilibili.com/video/BV18k4y1m7Ar/?share_source=copy_web&vd_source=4131627a2e94dad1eb4c895d415f7ad3

next[]数组求法

i 代表next数组位置指针,不回溯

j 代表回溯位置指针，如果遇到不匹配的字符，则寻找上一个字符的next值进行回溯

代码

void getNext(int* next, const string& s){
  next[0] = 0;
  int j = 0;
  for(int i=1; i<s.size(); i++){
    while(j>0 && s[i] != s[j]){
      j = next[j-1];
    }
    if(s[i] == s[j]){
      j++;
    }
    next[i] = j;
  }
}

基本逻辑：

• 结合代码来看，比较s[i] s[j]:
  • s[i] == s[j]: j++, next[i] = j //此处为了代码简洁美观，判断完两数是否相等后，先计算j，最后在给next赋值，准确解释应该是：if s[i] == s[j]: next[i] = j +1 ； i++，j++。
  • s[i]≠s[j]: j=next[j-1] ， //两数不相等的话，判断能否回溯，如果能，j回溯到j-1所对应的next值，再比较next[i]与next[j] ，如果仍旧不相等，继续回溯，直至相等或不满足回溯条件，如果不满足回溯条件，则给next赋值。
    • 回溯条件：j>0 && s[i] != s[j] // j最多回溯到0，因为回溯时 j=next[j-1] ，保证数组下标为非负，j-1 ≥ 0，则j>0.
    • s[i] ! = s[j] 回溯 j=0 仍旧不满足回溯条件，赋值next[i]=j,即next[1]=0

例子

字符串 s =“aabaabaaa” 所对应的next数组是多少？

是next[0,1,0,1,2,3,4,5,2]

计算步骤如下：

• j=0,i=1, next[0] = 0; 因为第一个next值默认为0

• i=1,j=0 s[1] == s[0] 相等 , 先j++，再赋值，j = 1，next[1] = j = 1；i++，i=2
  

• i=2,j=1 s[2] ! = s[1] 不等，看是否满足回溯条件 j>0 && s[i] != s[j] 满足，回溯。

  • j=next[j-1] = next[0] = 0, 再比较数组的值，s[2] ! = s[0] ,看是否满足回溯条件, j=0不满足，赋值， next[2] = j=0
  • i++,i=3

• i=3,j=0 s[3] ==s[0] j++ j=1, next[3] = 1, i++,i=4
• i=4,j=1 s[4] == s[1] j++,j=2 next[4] = 2, i++, i=5
• i=5,j=2 s[5]==s[2] j++,j=3 next[5]=3, i++,i=6
• i=6,j=3 s[6] == s[3] j++,j=4, next[6]=4, i++,i=7
• i=7,j=4 s[7] == s[4],j++,j=5, next[7]=5,i++,i=8
• i=8,j=5 s[8] ! = s[5] ,回溯，j=next[j-1]=next[4]=2,
  • s[8] ! = s[2], 回溯，j = next[j-1]=next[1] = 1,
  • s[8] == s[1] , j++,j=2, next[8]=2, i++,i=9
• i=9 跳出循环

使用next数组进行字符串匹配

过程描述：

如下例子来描述

例子：

文本串s：a b x a b c a b c a b y

模式串t： a b c a b y
step1:求模式串的next数组

按照上述步骤求得next=0 0 0 1 2 0

step2：s与t进行匹配

定义两个下标j 指向模式串起始位置，i指向文本串起始位置。如果两个字符相等，i++，j++

如果两个字符不相等，则查看前一个字符的next值，重新比较以此next值为下标的模式串的字符和文本串字符是否相等。

如上图所示：ab匹配，但x与c不相等，则需要查看c前面一个字符b的next值，为0，0指向a，于是比较x与a

如上图：x不等于a，所以i接着向前，指向a，比较a与a

a与a相同，i++，j++，b=b,c=c, a=a,b=b,c≠y

如上图：c与y不相等，则需要查看y前面一个字符b的next值，为2，2指向c，于是比较c与c

c=c,i++,j++,a=a,b=b,y=y

匹配完毕

代码

 int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }

步骤重复说明一下：

在文本串s里 找是否出现过模式串t。

文本串s：a b x a b c a b c a b y

模式串t： a b c a b y

定义两个下标j 指向模式串起始位置，i指向文本串起始位置。

i不回溯

i就从0开始，遍历文本串，代码如下：

for (int i = 0; i < s.size(); i++) 

接下来就是 s[i] 与 t[j] 进行比较。

如果 s[i] 与 t[j] 不相同，j就要从next数组里寻找下一个匹配的位置。

代码如下：

while(j > 0 && s[i] != t[j]) {
    j = next[j - 1];
}

如果 s[i] 与 t[j] 相同，那么i 和 j 同时向后移动， 代码如下：

if (s[i] == t[j]) {
    j++; // i的增加在for循环里
}

如何判断在文本串s里出现了模式串t呢，如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了。

匹配结束后，要在文本串中找出和模式串完全匹配时相匹配字符的**第一个位置 **（），所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置。

• 文本串s：a b x a b c a b c a b y
• 模式串t： a b c a b y
• return的是 a b c a b y 在 a b x a b c a b c a b y完全匹配时的第一个位置a，即6
• 完全匹配时，i指向11，j会在++一次，所以会指向数组长度6，所以 11-6+1=6

if (j == (t.size()) ) {//j指向了模式串t的末尾，j=6，此时i=s.size()-1
    return (i - t.size() + 1);
}

练习

参考：代码随想录：

首发在wolai笔记软件：
KMP算法 - https://www.wolai.com/soy7nmo4y3GDjM1HfUfUQ7

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

class Solution {
public:
    void getNext(int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i=1; i<s.size(); i++){
            while(j>0 && s[i] != s[j]){
            j = next[j-1];
            }
            if(s[i] == s[j]){
            j++;
            }
            next[i] = j;
        }
    }    
    int strStr(string haystack, string needle) {       
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};