• 关于KMP中部分匹配表的含义及使用方法，参见阮一峰的文章，那边简明扼要，这边不再赘述
  • next数组和部分匹配表的关系：next数组是将部分匹配表向右移动一格的结果。使用next数组而不是部分匹配表，是为了在KMP中表述更加方便，不用手动-1
  • 本文可直接看图，文字只做辅助描述，不包含必要信息。关键话语会高亮。

求解方式：递推

  • 由于next数组是部分匹配表右移一格，故初始值next[0]=0
  • 求解next[i]时，假定next[0]到next[i-1]都已知，通过递推方式计算next[i]
  • 递推的讨论过程：
    • next[i]可能是next[i-1]+1（如果读到的i处字符可以使得最长的相等前后缀都生长）
    • next[i]也可能比next[i-1]更小（如果读到的i处字符不能使得最长相等前后缀生长，就一定会回退），当回退时，需搜索出next[i]。该算法的精髓在于回退时如何搜索next[i]：尽量利用pattern的性质选出一些值进行判断，减小搜索空间

递推遇到的两种情况

  • 如图中第一种情况，读到多一个字符（i处）时，若最长相等前后缀可以生长（即加上i处字符后能构成相等前后缀），则next[i]=next[i-1]+1
  • 如图中后两种情况，读到多一个字符（i处）时，若最长相等前后缀不能生长，则需重新选择最长相等前后缀（回退），如何确定该回退到何处（即如何搜索next[i]）：
    • 在next[i-1]对应的最长相等前后缀（图中绿色）中继续找它的最长相等前后缀（图中黄色），这样做的理由是：最长相等前后缀的最长相等前后缀一定是次长的相等前后缀，当最长相等前后缀无法生长时，应该讨论次长相等前后缀是否可生长。若找到，则可由该黄色部分生长（判断黄色部分和i处字符是否能构成相等前后缀）
      • 若生长成功（图中第二种情况）则得到next[i]的值，return
      • 若生长失败（图像第三种情况）则继续该过程，查找黄色部分的最长相等前后缀
      • 只要生长失败就查找最长相等前后缀的最长相等前后缀，直到生长成功（图中第二种情况），或者找不到最长相等前后缀（图中第三种情况）
      • 上述查找过程迭代进行，而最长相等前后缀是由next数组界定的，即：子串str[0:j]的最长相等前后缀就是str[0:next[j]]，因此这个迭代查找最长相等前后缀的过程即是不断代入next数组的过程
      • 若直到最后无法找到最长相等前后缀（图中第三种情况），则认为原字符串中不存在任何长度的相等前后缀，此时像暴力解法一样直接从头开始比较即可。

KMP_next

KMP完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// Runtime: 4 ms, faster than 99.00% of C++ online submissions for Implement strStr().
// Memory Usage: 7.3 MB, less than 11.26% of C++ online submissions for Implement strStr().
class Solution {
public:
    int strStr(string str,string pat){
        if(pat=="") return 0;
        vector<int> next=get_next(pat);
        int j=-1;
        for(int i=0;i<str.size();++i){
            while(j>-1 && pat[j+1]!=str[i])
                j=next[j];
            if(pat[j+1]==str[i])
                ++j;
            if(j==pat.size()-1)
               return i-pat.size()+1;
        }
        return -1;
    }
private:
    vector<int> get_next(string pat){
        vector<int> next(pat.size(),-1);
        int j=-1;
        for(int i=1;i<pat.size();++i){
            while(j>-1 && pat[j+1]!=pat[i])
                j=next[j];
            if(pat[j+1]==pat[i])
                ++j;
            next[i]=j;
        }
        return next;
    }
};