題解：
https://leetcode-cn.com/problems/implement-strstr/solution/zhe-ke-neng-shi-quan-wang-zui-xi-de-kmp-8zl57/

• 重點： KMP算法的重點在txt字符串的指針不停往后跳+1，而pattern指針可以回溯。我們希望而當(dāng)出現(xiàn)壞字符的時候，txt指針不回溯，pattern指針往前回溯距離最短，耗時最低。

  
  
  image.png

• 問題來了，如何使txt指針i穩(wěn)定前進(jìn)，pattern指針j跳躍回溯最少？j回溯最少即pattern往后移動最多幾個格子不會出現(xiàn)遺漏case？涉及到了字符串的公共最長前后綴。使用該前后綴，即可快速知道pattern整體后移多少，j跳躍多少。如上圖所示，pattern后移2格是下一步最優(yōu)解。為何？因為此時bcb重合。若只移動一格則不匹配。而匹配這個條件就等價于匹配的子串是最長公共前后綴bcb。因此最多移動2格。有沒有可能遺漏？比如移動一格就匹配了？移動一格若匹配則說明子串是公共前后綴，此時才是真正的最長公共前后綴，與假設(shè)的移動2格最長不符。那能不能移動更多？不能，那樣會有遺漏case。因此移動2格是最優(yōu)解。

  • 即j移動到bcb后面一格。而若該步發(fā)現(xiàn)還是txt[i] != pattern[j]，那么需要pattern繼續(xù)后移動，即j繼續(xù)往前回溯。即需要找到當(dāng)前子串的第二長的公共前后綴。而第二長的公共前后綴就是最長公共前后綴本身的最長公共前后綴，
  • 這里我們來證明這一定理：假設(shè)pattern的最長公共前后綴是x，那么pattern的第二長公共前后綴y一定是x的最長公共前后綴。根據(jù)這一推論可輕松推廣到第N長的情況。這是kmp算法非常重要的一個定理，沒有它KMP就失去了高效性。通過這個定理就可以非?？斓鼗厮菡业阶址牡贜長公共前綴。證明如下圖所示：

image.png

若j回溯到一個位置，壞字符匹配上了，那j++，i++繼續(xù)循環(huán)。這是我們想看到的情況，即匹配的最優(yōu)解，j只回溯了幾次，i就繼續(xù)開始動了，且j也無需回溯到頭。且我們的證明也保證了無遺漏case。

若j回溯到頭，還是沒匹配上，那就i++，從j=0開始重新匹配了。盡管和暴力看似一樣，但是實際這一步，i直接跳過了之前匹配上的子串長度，且j回溯的非?？臁?/p>

偽代碼

• 一個for循環(huán)體內(nèi)：
  • 若txt[i] == pattern[j] ，則i++，j++，若j==len(pattern)則說明找到了，否則進(jìn)入下一個循環(huán)體。
  • 若txt[i] != pattern[j] pattern指針j跳躍到子串最長公共前后綴的前綴后一個位置。而txt指針i不變，再次進(jìn)行比較，若不同，則j繼續(xù)回溯到當(dāng)前子串（當(dāng)前子串=上一個子串的最長公共前后綴）的最長公共子串（=上一個子串的第二長最長公共后綴）的前綴位置+1……如此回溯直到找到txt[i]==pattern[j]或沒找到。找到則i++，j++，否則j移動到0，只有i++。之后進(jìn)入下一個循環(huán)體。

求pattern的最長公共前后綴

外層循環(huán)是O(N)，那么我們希望里層的循環(huán)是常數(shù)時間復(fù)雜度，即需要事先對pattern構(gòu)建一個next數(shù)組，next[i]代表了前i+1個字符串中最長公共前后綴的前綴末位的index。如下圖所示，next[4]=2即代表bcbcb的最長公共前后綴的前綴末位index=2，即長度=3=bcb。

image.png

由于next數(shù)組的構(gòu)建只與pattern有關(guān)，因此可以提前構(gòu)建一次，從而應(yīng)對各個txt。
我們希望構(gòu)建的時間復(fù)雜度是O(M)。構(gòu)建next的過程其實就是對next的每個前綴子串計算最長快樂前綴位置的過程。即leetcode另一題：https://leetcode-cn.com/problems/longest-happy-prefix/solution/ni-zhen-de-li-jie-kmpma-jiao-ni-xun-su-zhang-wo-bi/
而我們這里構(gòu)建的next數(shù)組就是這一題的增強版。這一題哪怕暴力計算一個字符串的最長公共前后綴，時間復(fù)雜度也是線性的。但是計算next數(shù)組就不是了，因此不能暴力求解。

next[0]=-1表示無公共的。之后就是一個dp問題。即知道了next[i-1]及其之前的值，推算當(dāng)前的，而非暴力遍歷。

這里我們可以證明：next[i]字符串的最長公共前后綴-1位（下圖中Y綠），是next[i-1]字符串的某個公共前后綴。
因為若新加了一位數(shù)，構(gòu)成了最大公共前綴，那么其前綴-1=后綴-1=原子串的某公共前后綴的后綴。因為一定是原子串的某個公共前后綴。而通過之前的證明可得，一定是其最大公共前后綴的最大公共前后綴的…………某一個。

image.png

因此，求next[i]只需要不?；厮?，比較pattern[i]與blue的公共前后綴的前綴后一位是否相等。否的話繼續(xù)往前回溯。是的話就找到了填入前綴的index。