KMP这个算法是专门为了解决字符串匹配和字符串子串匹配的一个经典算法。可以在O(n)内算出下列信息：
1. 两个字符串是否匹配，如果不匹配，最大长度是多少
2. 一个字符内是否有重复，如果有重复，重复了几次。
3.其他。。。
之前是跟小伙伴刷题的时候对这个问题产生了非常浓厚的兴趣。我自己在看的时候也看到了前辈们写的很好的文章们，比如
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
谷歌搜索第一名不是没有道理的。
我自己就借着他的文章总结一下。
1. 咱得引入一个概念 叫公共前缀后缀，啥叫公共前缀后缀呢？就是说，同一个字符串后缀等于前缀（不含自身）的连续子串。说概念太绕嘴，偷个图（来自引用链接）
2.引入下一个概念，最长公共前缀后缀。中文太长，英文叫border。就是所有的公共前缀后缀里面最长的那一个，还是那句话，重复不含自身。
我们把border这个概念用在全数组上，对于字符串下标i, border[i] 意味着S.substring(0,i+1)的最长公共前缀后缀。图里面border[5] = 1,因为最后一个A等于第一个A，border[6] == 2 因为最后两个AB等于第一个AB。这里看到了
公共前缀后缀的比较对象是不变的，永远是跟全字符串的前缀在比
公共前缀后缀不会突增，只会突减。
图中border[6] == 2了以后，border[7]==0了直接就。
那么问题来了，border每次回退，最少需要回退多少呢？（因为如果每次都是0，那跟暴力做法又有什么区别呢？）
3. 要证明的点如下：记一个字符串为S, S.substring(0,i) 所对应的border值是b，那么:
a. border==0 没有意义 直接跳过，因为 0 说明没有前缀等于后缀。也就是说，回退的时候，如果已经回退到0了，就不用继续算了，直接i++
b. 如果S.chatAt(i) != S.chatAt(b),最少需要回退的步数为b - border[b]。也就是说，下一个比较的就是S.chatAt(i) == S.chatAt(border[b])
c. 如果S.charAt(i) == S.charAt(b)，那么，i++; border(b) == b; b++;
阿诺。。。本人的数学证明实在太差，我们就先不证明了，记住这个结论（也不难记）
然后 我们就知道border怎么算了，代码如下
好了，那现在要问了，会算border了怎么字符串匹配呀？
好说啊，你知道s.length, p.length < s.length,假设 p s 都是alphanumerical的，这么算就行
1. String buffer = s + "#" + p; (s和p之间的分隔符可以使用任意特殊字符，保证border[indexOf(#)] == 0）
2. 算出border(buffer)[]的所有位
3. 如果任意时刻，border(buffer)[i] = p.length(); 发现匹配
好了 一个比较显著的应用就是leetcode 459。求整个字符是否是整数个子串的重复。你想我们算border就是多少后缀等于前缀。这道题目不就自然想到了要用kmp的border来做么
代码张这样，我参考了这个帖子
这里要说明的一点是把border算完以后我怎么知道有没有呢？我贴几个屏幕输出
我怎么知道上面一个是true，下面一个是false呢？
先再来一个例子
这就有点思路了吧？如果一个字符串是一个子串重复了k次整，那么到第k次的时候，假设下标为i 那么一定有
border[i] = (k-1) * pattern.length();
利用这个性质，我就可以有如下结论
1. 判断是否是整数次重复：看看是否S.length % (S.length - border[last entry]) == 0
2. 如果1.为真，几次重复：S.length / (S.length - border[last entry])
还有一个很经典的例子是leetcode 214 这可是一个hard的题目
这道题目怎么做呢？问你只在最前面加字符，怎么加能够加成最短palindrome
是吧，写在这里就已经耍赖了。这题目其实是在问你这道题KMP思路怎么做？
首先咱先来个比较明显的事实：
如果一个String s 是palindrome，那么kmp(s + "#" + new StringBuilder(s).reverse().toString()) 应该完全匹配，最后index显示s.length()
那要不是呢？我们看看最后一个index显示什么
对于任意字符串s， kmp(s + "#" + new StringBuilder(s).reverse().toString()) 的最后一个index显示的是这个字符串从0到border[index]是回文串。
到这里 比我聪明的同学就可以想到
new StringBuilder(s.substring(border[index])).reverse().toString() + s 就是我们要的答案了！
有人（就是某个三十岁了还在刷题的아저씨)说不对啊，那就不能加在中间么？
abdac 中间加个d，前头加个c 不就是cadbdac了么？
看题！说了只能在最前加字符！
好吧。。。
代码如下
网友评论