你可能聽過KMP這個名詞，先不用管KMP是什麼，看看下面的問題：
給你一個字符串"jail"，讓你在「abjacalisjaisnfljailnafa」中尋找該字符串是否存在。
第一次看到這道題的時候，上來就是一通暴力匹配，思路也很容易理解
該題暴力解法的基本思路是：用兩個指針分別指向字符串P和T的首個字符
一旦兩個指針指向的字符不同，字符串T的首個字符和P中的下一個位置重新開始匹配重複上述兩個步驟，直到兩個指針任意一個指針走到了字符串的結尾，循環截止；
如果T的指針的大小等於T的長度，說明匹配成功，否則，匹配失敗。
問題是可以解決，但是，其中很多步驟都是重複的，因為一旦匹配失敗，T字符又要從頭開始匹配，這樣是不是浪費了很多時間？
而生活中我們使用字符串匹配的地方是非常多的
我們所用的IDE、office辦公軟體、文本編輯器等等非常多的軟體中是不是都包含了文本查找、文本替換這些功能呢？
這個時候，KMP算法橫空出世
圖片中的內容截取於維基百科
說了這麼多，這個算法究竟是如何進行字符串查找的呢？
首先，該算法需要在開始匹配之前收集足夠的「信息」，用於在匹配過程中給出「指導意見」
這個「信息」指，根據待查找字符串T建立的一張表
如果長的字符串不容易得出答案，那我們嘗試從最短的字符串看看：
a：很明顯，它的公共前後綴長度為0
ab：公共前後綴長度為0，因為a != b
aba：公共前後綴長度為1，也是最長的，因為前後都有一個a
abab：最長公共前後綴長度為2
ababc：最長公共前後綴長度為0比較aba和abab，你能發現什麼？
在aba的基礎上加了一個字符，這個字符和第一個a後面的字符相同，所以在aba的基礎上，abab的最差公共前後綴長度為2
而在abab的基礎上加了一個c字符，整個字符串的公共前後綴的長度就變為了0，這是因為c字符和abab中的任何字符並不相等
發現規律了嘛？
從最小的開始比較，因為當一個字符作為子串的時候，公共前後綴的長度一定是0，就不用計算了，從第二個開始，也就是從ab開始，我們比較0位置和1位置是否相同，相同的話最長公共前後綴就是1，否則就為0
然後繼續看aba，比較新添加的字符和上一次求出的公共前後綴長度值的位置的字符是否相同，相同，用求出的上一個子串的公共前後綴長度加上1，aba的最長公共前後綴長度就為1
abab，還是上述步驟，看新添加字符和第[上一個子串的最長公共前後綴長度]個字符，也就是1位置和3位置，相同，那麼abab子串的最長公共前後綴長度=1+上一個子串的最長公共前後綴長度
那麼如何根據這個表來進行加速匹配呢？
匹配的過程中一定是按照相應的規則進行匹配的，對應的，table中的值可是大有用處的，先不說那麼多概念，最直觀的感受一下KMP算法是如何進行匹配的吧
上面的動畫中，我們讓字符串T在字符串P中進行匹配，如果在P中找到了T的存在，返回true，否則返回false；
匹配的規則還是一個字符對一個字符進行匹配，但是KMP算法神奇的地方就在於，當兩個字符沒有匹配成功的時候所採取的策略，這個策略並不是和暴力解法那樣：一旦一個字符沒有匹配成功，不管之前有多少個匹配成功，直接從頭再來。
這個策略依託的就是我們最開始建立的最長公共前後綴表
兩個字符匹配的時候，相安無事，兩個指針都往後移動；
一旦兩個字符沒有匹配成功，首先要做的就是拿到T指針的位置在table表中找出對應位置的值，這個值就是我們下一次要進行匹配的T字符串中起始位置
代碼：public boolean kmp(String resource, String target) {
int len = target.length();
if (len < 1) return false;
//確定最長公共前後綴表
int[] preTable = new int[len];
commonPrefix(target,preTable);
int i = 0,j = 0;//i指向resource j指向target
while (i < resource.length() && j < target.length()) {
//如果兩個指針指向的字符不同
if (resource.charAt(i) != target.charAt(j)) {
//根據最長公共前後綴表中j所在位置的值移動指針
//如果小於0，resource中的指針後移，j不動
if (preTable[j] < 0) {
i++;
} else {
//否則將指針j的位置修改為最長公共前後綴表中j位置對應的值（重新確定匹配位置）
j = preTable[j];
}
} else {
i++;
j++;
}
}
//如果指針j的長度等於target長度說明匹配成功，否則，失敗
return j == target.length();
}
//獲取target字符串的最長公共前後綴表
private void commonPrefix(String target, int[] preTable) {
int n = target.length() - 1;
if (n > 0 && n < 2) {
preTable[0] = -1;
return;
}
//為了編碼方便
preTable[0] = -1;
//一個字符的最長公共前後綴長度一定是0
preTable[1] = 0;
int index = 2;
int j = 1;
while (j < n) {
if (target.charAt(preTable[index - 1]) == target.charAt(j)) {
preTable[index] = preTable[index - 1] + 1;
} else {
preTable[index] = 0;
}
index++;
j++;
}
}感謝大家的閱讀，如果對文中內容有不同見解，希望不吝賜教。