題目
給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)。如果不存在，則返回 -1。
示例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2
要找出符合的字符串，最暴力的方法是通過兩個for循環(huán)來解決。
首先我們設(shè)置needle[0] 與haystack[0] 左邊對齊比較，如果相同就比較 needle[1] 與haystack[1]，如果不相同則讓needle右移一位，使needle[0] 與haystack[1] 對齊比較。如圖所示以此類推，直至找到結(jié)果。
這么做的結(jié)果是每次needle比較失敗，都會往后移動一格，然后重新從頭開始比較。最差的結(jié)果就是每次比對到最后一個才發(fā)現(xiàn)不對，這樣就要從第一位開始比對起，所以最壞的打算就需要O(m*n)。
為了優(yōu)化這個方法，我們可以采用KMP(The Knuth-Morris-Pratt Algorithm)算法，這樣我們可以更快一點解決問題，優(yōu)化算法為O(m+n)。
接下來用盡量簡潔的篇幅讓你明白這個偉大的算法。
算法邏輯：
首先聲明所有數(shù)組第一個下標從0開始。(有些教程會選擇從1開始，先說清楚，以免搞混了)。
這里我們使用一個例子來簡單說明一下
例如
如果我們用暴力尋找的話，那么過程是：
總共比對了 4 + 1 + 1 + 1 + 7 + 1 +1 + 1 + 3 + 1 + 1 + 8 +1 +1 +1 +8 = 41 (次)
如果改進成KMP的話，那么運算過程就是(灰色地方是KMP算法不去考慮的地方，紅點是每次比較的字符串位置)
總共比對了 4 + 1 + 7 + 1 + 1 +8 + 4 = 26 (次)
如果我們看紅點在abcxabcdabxabcdabcdabcy的位置，我們就會發(fā)現(xiàn)紅點一直在向前移動，不會往后退/回頭。這就是KMP算法的優(yōu)點即不會倒退(也有人稱作回溯)，所以就能避免不必要的匹配檢查。
讓我們依次看看KMP算法在上面的例子中都做了些什么。
首先讓我們看一下第一個例子。
綠框中是KMP算法跳過的地方，那么我們就來對比一下兩個紅框里面的內(nèi)容。
這里我們可以看到，深綠色方框那里是不相同字符的位置與新一輪判定的開始位置。
深橘黃色方框里的是已經(jīng)匹配成功的字符串 abc。
關(guān)鍵的地方來了，因為已經(jīng)匹配成功的字符串a(chǎn)bc中沒有相同的前后綴，所以下一次比對要從abcdabcy的首位開始比較。
我們簡單地來看一下abc的前后綴情況。
要注意，這里我們看的前后綴的長度要小于已匹配到的字符串長度，因為如果長度一樣了那就不用分前后綴了，也沒有比較的意義了。
因為沒有相同的前后綴，我們就不用擔心錯過什么，直接從配對失敗的地方開始新的匹配就行了。
這個很好理解，讓我們假設(shè)一下如果在上面這個例子中間有這么一種情況
在這里如果符匹配條件我們至少需要滿足方框內(nèi)的字符相同。
讓我們看看方塊內(nèi)的字符處于abc中的什么位置
在黃色框內(nèi)，bc屬于abc的后綴，ab屬于abc的前綴，所以如果條件符合的話，abc需要有相同的前后綴。
不理解為什么的同學不用擔心，現(xiàn)在只要記住我們在尋找相同前后綴就行了，一會看完應(yīng)該就能想通了。
讓我們看看下一個例子。
在這個例子中KMP算法跳過了綠色方框的部分，直接運行了紅色方框里的內(nèi)容。讓我們看看紅色方框里發(fā)生了什么
深綠色方框位置是不相同字符位置與新一輪比較的位置。
深橘黃色方框里的是已經(jīng)匹配的字符串 abcdab。
讓我們來找一下 abcdab的前后綴吧。
我們發(fā)現(xiàn)abcdab有相同的前后綴。
重點又來了，如果有相同的前后綴，我們就需要把前綴移動到后綴的位置上。
這樣abcdabcy就向右移動了四位，然后開始比較abcdabcy[相同前后綴長度] 上的字符，即第3個字符c(默認索引從0開始)。
不明白沒有關(guān)系，我們再看兩個例子。
在上面這個例子中，綠色依然是被忽略的部分，紅色方框是KMP算法執(zhí)行的部分。
讓我們繼續(xù)關(guān)注紅色方框里的內(nèi)容：
深綠色的地方是匹配到不一樣字符的位置，也是下一次比較的開始位置。
深橘色的地方是已經(jīng)成功匹配的字符串a(chǎn)b。
由于ab沒有相同的前后綴，所以下一次比較從abcdabcy開始。
最后我們看看這個例子
依舊只看紅色方框部分
深綠色的地方是匹配到不一樣字符的位置，也是下一次比較的開始位置。
深橘色的地方是已經(jīng)成功匹配的字符串a(chǎn)bcdabc。
讓我們來看看abcdabc的前后綴吧。
我們發(fā)現(xiàn)abcdabc有相同的前后綴abc，我們就需要把前綴移動到后綴的位置上。
這樣abcdabcy就向右移動了四位，然后開始比較abcdabcy[相同前后綴長度] 上的字符，即第3個字符d(默認索引從0開始)。
最后我們比對發(fā)現(xiàn)找到了目標字符串。
通過上面的例子，我們發(fā)現(xiàn)每當我們匹配失敗，就需要尋找匹配成功的字符串中有沒有相同的前后綴（最長的前后綴），然后再判定下一次比較要從哪一位開始。
邏輯實現(xiàn)：
還是回到上面的例子，如果每次匹配失敗都去判定一次是否有相同前后綴的話，那么就太麻煩了，所以我們可以在匹配前就把各種情況的前后綴找出來。
上面是我們能列舉出來的所有情況，KMP算法需要的關(guān)鍵信息就是最左邊的匹配數(shù)與最右邊的前/后綴長度。
因為8匹配就匹配完成，所以我們其實只需要考慮0～7匹配的情況，總共8種情況。
我們可以用一組數(shù)組來保存此數(shù)據(jù)，我們命名此數(shù)組為next數(shù)組。
int[] next = new int[] { 0,0,0,0,0,1,2,3};
所以每當我們匹配失敗的時候，我們就可以通過next數(shù)組來快速定位下一個需要對比的索引位置。
這樣我們的KMP算法可以理解為
KMP(string target, string txt){
1）計算next數(shù)組
2）通過循環(huán)來對比target與txt字符串
}
代碼實現(xiàn)：
1. next數(shù)組
這里推薦一下個人覺得不錯的視頻，如果感興趣的話可以深入了解一下https://www.bilibili.com/video/BV1Ys411d7yh?05:33，在5分33秒的時候開始講解next數(shù)組的邏輯。（Ps：相信我，一遍可能看不懂，看三遍肯定會看懂了?。。。?br>
整體的邏輯流程如圖所示：
代碼如下：
private int[] GetNext(string str){
int[] next = new int[str.Length];
next[0] = 0;
int i = 1;
int j = 0;
while(i < str.Length)
{
if (str[i] == str[j])
{
j++;
next[i] = j;
i++;
}
else
{
if (j == 0)
{
next[i] = 0;
i++;
}
else
{
j = next[j - 1];
}
}
}
return next;
}
2. KMP 算法的比較邏輯
然后我們再來梳理一下KMP算法取得next數(shù)組之后的邏輯。
很多人喜歡寫做i，j。其實就是haystack與needle的下標，用hi 與 ni 來表示的話個人感覺會清晰一點。
代碼可以寫作：
private int KMP(string haystack, string needle)
{
int[] next = GetNext(needle);
int hi = 0;
int ni = 0;
while (hi < haystack.Length) {
if (haystack[hi] == needle[ni]) {
ni++;
hi++;
}
if (ni == needle.Length)
{
return hi - ni;
}
else if (hi < haystack.Length && haystack[hi] != needle[ni])
{
if (ni != 0)
ni = next[ni - 1];
else
hi++;
}
}
return -1;
}
接下來我們就可以寫出KMP的主方法了。
private int KMP(string haystack, string needle)
{
int[] next = GetNext(needle);
int i = 0;
int j = 0;
while (i < haystack.Length) {
if (haystack[i] == needle[j]) {
j++;
i++;
}
if (j == needle.Length)
{
return i - j;
}
else if (i < haystack.Length && haystack[i] != needle[j])
{
if (j != 0)
j = next[j - 1];
else
i++;
}
}
return -1;
}
在運行KMP之前對輸入?yún)?shù)進行一些簡單的校驗：
if (string.IsNullOrEmpty(needle))
{
return 0;
}
if (needle.Length > haystack.Length || string.IsNullOrEmpty(haystack))
{
return -1;
}
所以全部代碼為：
public class Solution {
public int StrStr(string haystack, string needle)
{
if (string.IsNullOrEmpty(needle))
{
return 0;
}
if (needle.Length > haystack.Length || string.IsNullOrEmpty(haystack))
{
return -1;
}
return KMP(haystack,needle);
}
}
private int KMP(string haystack, string needle)
{
int[] next = GetNext(needle);
int i = 0;
int j = 0;
while (i < haystack.Length) {
if (haystack[i] == needle[j]) {
j++;
i++;
}
if (j == needle.Length)
{
return i - j;
}
else if (i < haystack.Length && haystack[i] != needle[j])
{
if (j != 0)
j = next[j - 1];
else
i++;
}
}
return -1;
}
private int[] GetNext(string str){
int[] next = new int[str.Length];
next[0] = 0;
int i = 1;
int j = 0;
while(i < str.Length)
{
if (str[i] == str[j])
{
j++;
next[i] = j;
i++;
}
else
{
if (j == 0)
{
next[i] = 0;
i++;
}
else
{
j = next[j - 1];
}
}
}
return next;
}
結(jié)語
感謝牛客大佬bailixi的講解，本文主要是大佬在leetcode上的講解并對其中錯誤地方進行了更正。如果在文中還有說錯的地方或有疑惑的地方請留言告訴我，我看到了會盡快回復(fù)！希望幫助大家一起理解KMP算法，覺得不錯的話也請點個贊，謝謝！?。?！
這里附上大佬的講解鏈接：
https://leetcode-cn.com/problems/implement-strstr/solution/c-kmp-xi-wang-wo-jiang-ming-bai-liao-kmpsuan-fa-by/
