Knuth–Morris–Pratt
刚到美国没多久，第一次接触刷题和算法的时候，第一课就是strStr，当时就听说了KMP，第一印象的KMP是一种晦涩难懂，fancy且不好实现，面试官也写不出来，在面试中写出来有炫技嫌疑的算法。当时思想学了个大概但没有重视，写当然是写不出的。
现在的我还是不会写，但是KMP无论是在leetcode还是各论坛出现频率过高，可以说到处都是都被提交烂了，所以这次下定决心好好学一遍这个一直被提及但从没写过的算法。
28. Implement strStr()
我们在一个string（haystack）里面找有没有和给定的另一个string（needle）匹配的一段sub string。
最简单的想法应该是我们用两个指针，i和j，i指向haystack，j指向needle，两个都从左向右扫，先移动i，直到i在haystack内找到了一个字符可以匹配到needle的第一个字符，这时i和j再一起向右，每次都判断i和j指向的字符是否匹配，匹配就扫下一个，不匹配就回到起点重新找。
最简单的思路，除了超时没什么大毛病，写出来也不难。
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null && needle == null || haystack.length() == 0 && needle.length() == 0) return 0;
if (needle == null || needle.length() == 0) return 0;
int i = 0;
int j = 0;
while (i < haystack.length()) {
while (i < haystack.length() && haystack.charAt(i) != needle.charAt(0)) i++;
int index = i;
while (index < haystack.length() && j < needle.length()) {
if (haystack.charAt(index) != needle.charAt(j)) break;
if (j == needle.length() - 1) return i;
index++;
j++;
}
j = 0;
i++;
}
return -1;
}
}
这里面有一个浪费时间的地方，就是i指针，在一些坏情况下，i指针可能要走很多回头路，可能前面都匹配，最后一个字符匹配不上，那么i就要回到起点，比如：
i指针反复倒退是时间复杂度很高的原因，那有没有一种方法能够让i不走回头路，只让j指针动？这就是KMP研究的结果。
我们观察下图，D字符没能匹配，但前面的AB两个其实已经匹配了，也就是说needle后面的字符和前面开头的字符有重复的地方，这就是降低时间复杂度的关键。那这时i指针原地不动，我们让j倒退到匹配的下一个，不就省下了AB两步匹配的时间吗。而且i指针从头走到尾不会有回头路。
问题在于如何知道j指针倒退到哪个位置，这就需要借助额外的存储index的数组。
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack.length() < needle.length()) return -1;
if (needle.length() == 0) return 0;
int j = 0;
int[] next = getNext(needle);
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;
}
private int[] getNext(String needle) {
int[] next = new int[needle.length()];
int k = 0;
for (int i = 1; i < needle.length(); ++i) {
while (k > 0 && needle.charAt(i) != needle.charAt(k)) {
k = next[k - 1];
}
if (needle.charAt(i) == needle.charAt(k)) {
k++;
}
next[i] = k;
}
return next;
}
}
next[] 里的 k = 正确 match 的长度
next[] 中，每个位置的数字是由 k 赋值的，代表“如果下一个字符串挂了，在我这个位置截止的字符串正确 match 的长度是多少”
于是这个 getNext() 函数就很好解释了。 next[] 的大小等于 pattern 长度，k 初始值为 0.
next[0] = 0 因为 substring 长度如果只为 1 的话，前面没东西和它匹配。
于是开始一个 while 循环，迭代寻找如果当前字符串挂了，我们目前的最长 suffix 到底多长，有可能会跳很多步。这个写法有点类似于 disjoint set 里面 - weighted union-find 的 path compression 实现，就是一个 while 循环迭代赋值 index 一直到正确的 / base case 为止。 k > 0 这个条件很重要，不然如果在第一个字符串挂了之后，会去找 next[-1] 就越界了。
每次我们在 index k 上挂的时候，是去找 next[k - 1] 的 k 值是什么。原因是 length 与 index 间有 1 的 offset ，我们去看 index = k 的位置- - 其实是在考虑要不要把 length 设成 k + 1.
此后如果当前字符串匹配，就把 k + 1，赋值到当前 next[i] 上。赋值之后就不会再改了。
match 函数的逻辑基本和 getNext 完全一样，k 代表目前的 text 上 match pattern 的字符串长度。
当 q = pattern.length() 的时候，从 i 开始往回挪动 q 步，因为挪动前 i 处在 pattern 最后一个字符，要再往回挪动一个位置。
i - needle.length() + 1;
214. Shortest Palindrome
思路不难想，如果string S不是一个回文，加上一段字符P，我们最后想要得到的回文结果可能是 PS = PQP'
这里面S == QP == QP'，P'是P的回文。那么很明显，Q也需要是一段回文。我们又想要加上的这段字符P尽可能的短，也就是说Q要尽可能长。
问题就变成了找一段string的最长前缀回文。
在这里，直接用一个 isPalindrome 函数去判断一个 substring 是不是 palindrome，然后从给定的 string 左面开始一直往右扫，去找到从最左边字符开始，最长的 palindrome，这样做显然是直觉的想法，但时间复杂度太高，逐个 substring 去调用 O(n) 时间的函数。
时间复杂度太高是因为没有深刻理解和利用palindrome的性质。
思路是对的，但要优化时间，这就用到了KMP算法。
leetcode论坛里面有一个帖子非常detail，就像我前面说的，KMP无处不在。（底下还有个ID叫晓美焰的要求用中文解释一遍，我也是惊了，不给你解释你要砍别人的头吗？）
KMP 算法的核心是 next function ，在 currect position 不匹配的情况下，在之前的substring中寻找最长的 suffix 后缀，使得它和 substring 中的 prefix 前缀相同。
如果我们的字符串可以分拆成两段 S = QP， 我们想要求的是最长的 palindrome Q. 设 S' 为 String S 的反序字符串，给定 SS' = QPP'Q' ，由于 Q 是 palindrome，可知 Q = Q'，二者分别是是 SS' 的前缀与后缀，因此可以直接通过计算 SS' 的 failure function 求出 Q 的最大长度。
真的很巧妙对不对，KMP算法的failure function，也就是后缀匹配前缀长度数组的function可以拿来算一个string的最长回文前缀的长度。如果没有这样一道题，很难往这种地方去想这个用法。
而且最终的代码非常的简洁，一个KMP算法的failure function和三行判断代码。
public class Solution {
public String shortestPalindrome(String s) {
if (s.length() <= 1) return s;
int[] next = kmp(s + "#" + new StringBuilder(s).reverse().toString());
int length = next[next.length - 1];
return new StringBuilder(s.substring(length)).reverse().toString() + s;
}
private int[] kmp(String pattern) {
int[] next = new int[pattern.length()];
int k = 0;
for (int i = 1; i < pattern.length(); ++i) {
while (k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
k = next[k - 1];
}
if (pattern.charAt(k) == pattern.charAt(i)) {
k++;
}
next[i] = k;
}
return next;
}
}