KMP String Pattern Matching

前言

KMP算法，之前都没有听说过，考研竟然要考？？excuse me？不过了解了之后，发现，这个算法还是很有用，同时也是很经典的，在此将自己的学习历程以及总结记录下来。

KMP算法

来源

由字符串模式匹配引进的。

直观来看，对于字符串匹配，也就是strstr()函数的功能，首先想到的是直接的遍历比较，对于长度为m的字符串以及长度为n的pattern，复杂度是O(m * n)。而应用KMP算法，可以将时间复杂度降到O(m + n)。

基本思想

这个到处都有说，各种“循循善诱”引出的。简单来说，就是：
对于pattern，当比到第k位，发现不匹配了，这个时候，前k位匹配的自己其实已经知道是什么了，所以这一段的最后一部分，可能和pattern的前一部分相同，直接从这之后开始比就好了。

这样一来，扫字符串的时候，指针是不用往后挪的，当到达p位置发现pattern的第k位不匹配，此时，string的[p-k, p-1]这一段和pattern的[0, k-1]这k位是匹配的。
如果是原来，那么string的指针得回去，从现在的p回到p-k+1的位置，然后pattern也向前挪一位比较。KMP的话，不把string的指针往后挪，而是只把pattern向前挪，当然，相同的就对齐，比较之后的了。

于是，pattern挪的距离就成了关键。对于[0, k-1]这k位，如果有相同的前缀和后缀，那么就挪到前缀和原来后缀这一段对齐。

具体操作

1. next数组

next数组是什么呢：

1	next[i] = pattern[0, i-1]这一子串的最长相同前后缀

比如说ABCABD，在D处，也就是next[5]为2。
另外，规定next[0] = -1。

其实，这样的说明个人是非常不喜欢的，只说了是什么，并没有说为什么这样定义，只知道这样后边要用到，然后就能够解决问题。就像好多线代教材上的证明，我看的过程中很恼火，你倒是告诉我为什么要这样做，鬼才想得到这里。

那么这里为什么要算next呢，算了有什么用呢？

这里next数组有两层意思，一个就是上边说的这个位置之前的子串的最长相同前后缀长度；另一个是，下一次比较时，在pattern的第j位开始比较。这两者本质上是一致的。

如果之前有k位的相同前后缀，即next[j] = k，那么，说明前k位[0, k-1]可以对齐到原来后缀的位置，而开始比较新的，可以从第k位开始比。

这样一来，这个next数组就直接告诉了我们，当string中的指针i不后退的时候，pattern中的指针应该从何处开始。

2. 计算next数组

先上伪代码：

def genNext(string p):
    n = p.length
    for i in [0, n):
        next[i] = 0
    next[0] = -1
    curr = -1 # [1]
    i = 0
    while i+1 < n:
        if curr == -1 or p[i] == p[curr]:
            curr++
            i++
            next[i] = curr
        else:
            curr = next[curr] # [2]
    return next

这个代码还是很短的，但其实并不是很好理解，至少对我来说..

curr代表当前相同前后缀的长度，同时也可以当做下标用，这个上文讨论过类似的用法

有两个点需要注意，在代码中已经标出：

[2] `curr = next[curr]`

先看第二点，curr = next[curr]，if后边的很好理解（先忽略curr == -1的判断），就是相同的话，往前走就是了，下一位的next就是curr加之后的结果。如果不相等，就有趣了，并不是相同前后缀的长度就是0了，没有最长，还有第二长嘛：

              p         i
        0 1 2 3 4 5 6 7 8 9
        a b a c d a b a b x
next   -1 0 0 1 0 0 1 2 3 2

如上图，curr(p)和i到达如图所示的位置，发现s[3]和s[8]并不相同，但这时不能简单的认为这一段就没有相同的前后缀，虽然之前最长的a b a无法延续下去，但是说不定次长的还可以。

次长的是什么呢？其实就是[0, p-1]这一段的最长相同前后缀！

于是，就有了curr = next[curr]

这样一来，p变为1，再去比较s[1]和s[8]时，发现相等了，这样就可以愉快的前进了。

[1] -1的使用

出现了3处-1，这其实算是算法设计中的一个小trick吧，用于控制边界条件。

跟[1]有联系，在curr = next[curr]过程中，curr其实一直再找更短的最长相同前后缀，所以curr一直再往后退，那么什么时候是个头呢？就是根本没有共同的前后缀，那么必然会出现curr = next[curr] = 0的情况，这时，下一步的时候，next[curr]也就是next[0]该有一个合适的值，让这个后退的过程停下来，这里取了-1。
于是，也就有了if判断时候的curr == -1，停下，curr赋0（正好+1是0，用-1也有这个好处），然后赋给next。
至于初始curr = -1，是初始化的技巧。如果不这样，可能还需给s[1]赋初值，这样不够优雅，也增添了好多判断的麻烦等等。

3. 计算字符串模式匹配位置

def kmpMatch(s, p):
    next = genNext(p)
    i = 0
    j = 0
    while i < s.lenth && j < p.length:
        if j == -1 || s[i] == p[j]:
            i++
            j++
        else:
            j = next[j]
    if j == p.length:
        return i - j

精巧啊，这个KMP算法，求next以及之后的匹配，第一次看到原理及实现，真的是觉得很精巧，值得反复揣摩。

应用

1. 字符串匹配（`strstr()`实现）

LeetCode 28. Implement strStr()

class Solution {
private:
    void genNext(string& p, vector<int>& next) {
        next[0] = -1;
        int i = 0;
        int j = -1;
        int n = p.length();
        while (i + 1 < n) {
            if (j == -1 || p[i] == p[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
    }
public:
    int strStr(string s, string p) {
        if (p.empty())
            return 0;
        vector<int> next(p.length(), 0);
        genNext(p, next);
        int i = 0;
        int j = 0;
        int sLen = s.length(), pLen = p.length();
        while (i < sLen && j < pLen) {
            if (j == -1 || s[i] == p[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pLen) {
            return i - j;
        } else {
            return -1;
        }
    }
};

算是上述算法的一个C++实现吧，没有一句多余的废话。

另外注意一点，如果有负数，和s.size()，s.length()之类无符号数比，会有问题哦，记得转成有符号数，或者采用其它方法防止之类的问题。

2. 重复子串问题

LeetCode 459. Repeated Substring Pattern

class Solution {
private:
    void genNext(string& s, vector<int>& next) {
        next[0] = -1;
        int i = 0;
        int j = -1;
        int len = s.length();
        while (i < len) {
            if (j == -1 || s[i] == s[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
    }
public:
    bool repeatedSubstringPattern(string s) {
        if (s.empty())
            return true;
        vector<int> next(s.length() + 1, 0);
        genNext(s, next);
        return (next[s.length()] != 0) && (s.length() % (s.length() - next[s.length()]) == 0);
    }
};

参考资料

阮一峰: 字符串匹配的KMP算法
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

很详细的 KMP 算法讲解，逻辑清晰，易懂
https://juejin.im/entry/58edc67461ff4b006925d2e9

前言