KMP這個算法是專門為了解決字符串匹配和字符串子串匹配的一個經(jīng)典算法?？梢栽贠(n)內(nèi)算出下列信息：
1. 兩個字符串是否匹配，如果不匹配，最大長度是多少
2. 一個字符內(nèi)是否有重復(fù)，如果有重復(fù)，重復(fù)了幾次。
3.其他。。。
之前是跟小伙伴刷題的時候?qū)@個問題產(chǎn)生了非常濃厚的興趣。我自己在看的時候也看到了前輩們寫的很好的文章們，比如
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
谷歌搜索第一名不是沒有道理的。
我自己就借著他的文章總結(jié)一下。
1. 咱得引入一個概念 叫公共前綴后綴，啥叫公共前綴后綴呢？就是說，同一個字符串后綴等于前綴（不含自身）的連續(xù)子串。說概念太繞嘴，偷個圖（來自引用鏈接）
2.引入下一個概念，最長公共前綴后綴。中文太長，英文叫border。就是所有的公共前綴后綴里面最長的那一個，還是那句話，重復(fù)不含自身。
我們把border這個概念用在全數(shù)組上，對于字符串下標(biāo)i, border[i] 意味著S.substring(0,i+1)的最長公共前綴后綴。圖里面border[5] = 1,因為最后一個A等于第一個A，border[6] == 2 因為最后兩個AB等于第一個AB。這里看到了
公共前綴后綴的比較對象是不變的，永遠(yuǎn)是跟全字符串的前綴在比
公共前綴后綴不會突增，只會突減。
圖中border[6] == 2了以后，border[7]==0了直接就。
那么問題來了，border每次回退，最少需要回退多少呢？（因為如果每次都是0，那跟暴力做法又有什么區(qū)別呢？）
3. 要證明的點如下：記一個字符串為S, S.substring(0,i) 所對應(yīng)的border值是b，那么:
? ? ? ? ? ? ? ? a. border==0 沒有意義 直接跳過，因為 0 說明沒有前綴等于后綴。也就是說，回退的時候，如果已經(jīng)回退到0了，就不用繼續(xù)算了，直接i++
? ? ? ? ? ? ? ? b. 如果S.chatAt(i) != S.chatAt(b),最少需要回退的步數(shù)為b - border[b]。也就是說，下一個比較的就是S.chatAt(i) == S.chatAt(border[b])
? ? ? ? ? ? ? ? c. 如果S.charAt(i) == S.charAt(b)，那么，i++; border(b) == b; b++;
? ? ? ? ? ? ? ? 阿諾。。。本人的數(shù)學(xué)證明實在太差，我們就先不證明了，記住這個結(jié)論（也不難記）
然后 我們就知道border怎么算了，代碼如下
好了，那現(xiàn)在要問了，會算border了怎么字符串匹配呀？
好說啊，你知道s.length, p.length < s.length,假設(shè) p s 都是alphanumerical的，這么算就行
1. String buffer = s + "#" + p; ?(s和p之間的分隔符可以使用任意特殊字符，保證border[indexOf(#)] == 0）
2. 算出border(buffer)[]的所有位
3. 如果任意時刻，border(buffer)[i] = p.length(); 發(fā)現(xiàn)匹配?
好了 一個比較顯著的應(yīng)用就是leetcode 459。求整個字符是否是整數(shù)個子串的重復(fù)。你想我們算border就是多少后綴等于前綴。這道題目不就自然想到了要用kmp的border來做么?
代碼張這樣，我參考了這個帖子
這里要說明的一點是把border算完以后我怎么知道有沒有呢？我貼幾個屏幕輸出
我怎么知道上面一個是true，下面一個是false呢？
先再來一個例子
這就有點思路了吧？如果一個字符串是一個子串重復(fù)了k次整，那么到第k次的時候，假設(shè)下標(biāo)為i 那么一定有
border[i] = (k-1) * pattern.length();
利用這個性質(zhì)，我就可以有如下結(jié)論
1. 判斷是否是整數(shù)次重復(fù)：看看是否S.length % (S.length - border[last entry]) == 0?
2. 如果1.為真，幾次重復(fù)：S.length / (S.length - border[last entry])
還有一個很經(jīng)典的例子是leetcode 214 這可是一個hard的題目
這道題目怎么做呢？問你只在最前面加字符，怎么加能夠加成最短palindrome
是吧，寫在這里就已經(jīng)耍賴了。這題目其實是在問你這道題KMP思路怎么做？
首先咱先來個比較明顯的事實：
如果一個String s 是palindrome，那么kmp(s + "#" + new StringBuilder(s).reverse().toString()) 應(yīng)該完全匹配，最后index顯示s.length()
那要不是呢？我們看看最后一個index顯示什么
對于任意字符串s， kmp(s + "#" + new StringBuilder(s).reverse().toString()) 的最后一個index顯示的是這個字符串從0到border[index]是回文串。
到這里 比我聰明的同學(xué)就可以想到
new StringBuilder(s.substring(border[index])).reverse().toString() + s 就是我們要的答案了！
有人（就是某個三十歲了還在刷題的???)說不對啊，那就不能加在中間么？
abdac 中間加個d，前頭加個c 不就是cadbdac了么？
看題！說了只能在最前加字符！
好吧。。。
代碼如下
