KMP算法

在探索文本串以前，模式串要先了解自己

一、介绍

KMP主要应用在字符串匹配上。

主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

next数组就是一个前缀表（prefix table）。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

二、前缀表

(一）例子

模式串：

我们假设有这样的文本串，？表示的字符我们并不关心：

将文本串和模式串进行匹配：

我们发现，在*-f匹配时不对应，我们只知道*和f匹配不对应，并不知道*是除f外的什么字符。

此时，一个很显然的减少匹配次数的思路是将模式串后移，让*和b进行比较:

再在文本串中寻找算法有与模式串匹配的部分。

（二）前缀表

通过前面的例子，我们很容易发现，我们的目标是：在当前的字符匹配失败的情况下，给出模式串应该从什么位置开始，和当前文本串的字符匹配。

为此引入前缀后缀概念，前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

例子：
字符串aab，最长相同前后缀的长度为0。
字符串aaba，最长相同前后缀的长度为1，即前缀：aaba和后缀：aaba。
字符串aabaa，最长相同前后缀的长度为2，即前缀：aabaa和后缀：aabaa。
字符串abcfabc，最长相同前后缀的长度为3，即前缀：abcfabc和后缀：abcfabc。

那么模式串中从第一个字符到当前字符的子串的最长相同前后缀的长度就是对应前缀表的数值。

例子：

可以看出模式串与前缀表对应位置的数字表示的就是：在此字符之前的的模式串子串中，有多大长度的相同前缀后缀。

三、next数组

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一之后作为next数组。

其实这并不涉及到KMP的原理，而是具体实现，next数组即可以就是前缀表，也可以是前缀表统一减一。

我们以next数组即前缀表为例：

    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }

对于while循环，每次while循环实际上就是，在当前的字符匹配失败的情况下，给出模式串应该从什么位置开始，和从开头到i位置的模式串子串的字符匹配，找出最长相同前后缀。

通过上面while循环的条件有两个：

• 1、没有匹配的前缀和后缀

• 2、可以从当前位置继续匹配前缀和后缀

四、KMP代码

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 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;
    }
};