KMP算法

背景

判断str是否包含pattern。比如str=ABABABCABABABCABABABC,pattern=ABABC。

暴力方法

同时遍历str和pattern，当遇到不匹配时，str重新遍历起始位置+1，pattern从0重新开始。这样下来时间复杂度是O(m*n)。

KMP算法

同时遍历str和pattern，当遇到不匹配时，str的指针并不会回退，只有pattern的指针会根据情况回退。时间复杂度为O(m+n)。

如何理解KMP算法（关键）

怎么使用的？

得到next数组，其中存放的next[i]表示[0, …, i]的最长相等前后缀，其中前缀表示以0开头，不包含i的子串，后缀表示以i结尾不包含0的子串。
当遇到不匹配时，pattern的指针移动next[j-1]处，重新开始遍历。

为什么保存最长相等前后缀就可以做到匹配？

考虑一个例子：str = abababc，pattern = ababc。以 i 表示str的指针，以 j 表示pattern的指针。

可以发现，在0-3，str[i] == pattern[j]，此时都顺利匹配；直到str[4]为a，pattern[4]为c，此时发生不匹配。

那么注意到，当我们在位置idx处发生不匹配时，意味着 pattern 中的[0, idx-1]都是匹配的，放到str中做一个简单的计算，那就是[i-idx, i-1]处都是匹配的。换到上面的例子中区，也就是 str 中的 abababc 和 pattern中的 ababc是匹配的。

所以此时我们还有必要将指针 i 或 j 从头再来吗？没必要！为什么？因为前面匹配的子串 abab中，我们可以直接从str的后缀，pattern的前缀分别开始遍历！ 也就是从 str 的后缀 ab，pattern的前缀ab开始遍历，这两个一定是相等的（最长相等前后缀）。

又因为str的后缀是以 i -1 结尾，所以当发生不匹配时，指针 i 不用动就可以了。那指针 j 就要移动到pattern的[0, j-1]的最长前缀的后一个位置去了，也就是next[j-1] 。（注意这里next保存的是最长前后缀的长度，对应到下标后，next中的值就是前缀的后一个位置的下标）

总结：主要是利用了不匹配位置处 j 的左侧，pattern的[0, j-1]都是匹配的，那么可以将j移动到[0, j-1]的最长相等前缀的后一个位置，也就是next[j-1]，此时 i 也恰好位于对应最长相等后缀的下一个位置，然后再重新遍历判断是否相等就可以了。

怎么得到next数组？

还是以 pattern = ababc 为例，我们得到他的next数组，也要用两个指针，指针 j 指向表示前缀的后一个位置，指针 i 指向当前要计算的next值的位置。

当 pattern[j] == pattern[i] 时，这不就是前缀的后一个位置等于后缀的后一个位置嘛，所以j++, next[i] = j;。

重点来了，当pattern[j] != pattern[i]时，怎么处理的？这时我们也要注意到，此时 pattern[0, j-1]和pattern[i-j, i-1]都是匹配的，而当 i，j 位置处不匹配了时，我们没办法做到 pattern[0, j] 和 pattern[i-j, i] 匹配了。

此时，我们就要考虑其中的子前缀和子后缀了，也就是：

1. [0, j-1] 和 [i-j, i-1]中，我们要找到最长的相等前后缀 [0, j-1-k] 和 [i-j+k, i-1]；
2. 然后继续判断 j-1-k+1 和 i 这两个位置是否匹配；
3. 如果成功匹配，那就是 pattern[0, j-k] 和 pattern[i-j+k, i]是一个最长的相等前后缀，next[j]就可以等于j-k+1了；
4. 如果不成功呢？继续回退（循环），直到 j 为0或者成功匹配。

那 k 是多少呢？

1. 前面说了是要找到 [0, j-1] 和 [i-j, i-1 ] 中最长的相等的前后缀的，那不就是下标为 next[j-1]之前的前缀嘛~，也就是说 j-1-k = next[j-1]-1
2. 那么因为我们要继续判断 j-1-k+1 和 j 这两个位置是否匹配，而且 j-1-k+1 = j-k = next[j-1]，所以当我们发生不匹配时，要将 j 移动回 j-k 也就是 next[j-1] 处，以继续判断是否匹配。
3. 如果匹配了，那么next[j]就可以等于j-k+1了，也就是next[j-1]+1了，鉴于代码中已经执行j = next[j-1]，所以，此时其实就是j++, next[j] = j了。
4. 如果不匹配，循环回退，直到j=0，next[j] = j = 0。

代码实现：

public int[] getNext(String s) {
	int j = 0;
	next[0] = 0;
	for (int i = 1; i < s.length(); i++) {
	    while (j > 0 && s.charAt(j) != s.charAt(i)) 
	        j = next[j - 1];
	    if (s.charAt(j) == s.charAt(i)) 
	        j++;
	    next[i] = j; 
	}
	return next;
}

最后，完整KMP实现

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = getNext(needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
	public int[] getNext(String s) {
		int j = 0;
		int[] next = new int[s.length()];
		next[0] = 0;
		for (int i = 1; i < s.length(); i++) {
		    while (j > 0 && s.charAt(j) != s.charAt(i)) 
		        j = next[j - 1];
		    if (s.charAt(j) == s.charAt(i)) 
		        j++;
		    next[i] = j; 
		}
		return next;
	}
}

其实，会发现str和pattern的匹配过程和得到next数组的过程很像，这是因为得到next的过程其实可以看做pattern自己和自己匹配的过程，只不过是前缀为 pattern 和后缀为 str 的匹配。

ps

上面我的实现中，next数组存放的是长度，也可以看做是最长前缀的后一个位置的下标。但有些实现中，next数组存放的是长度-1，就可以看做是最长前缀中最后一个位置的下标。因此代码可能会有出入，但这只是实现问题，不设计KMP算法本身。