⑴ 演算法-KMP
大一下參加學校ACM預備隊集訓的時候首次接觸KMP演算法，當時看了很多介紹文章，仍然不是很理解其實質，只是簡單地套模板AC題目，待大二數據結構與演算法課堂上再聽老師介紹一次，才恍然大悟其實KMP也就是那麼回事嘛。但當初為啥看那麼多文章都沒弄明白呢？正巧最近和朋友聊天時他告訴我他對KMP不是很理解，於是打算自己寫一篇文章，鞏固自己對KMP的認識，也希望能夠幫助更多朋友理解KMP。
在開始之前，需要知曉的概念：
前綴：以原串串頭為自身串頭的子串，如 的前綴有：
後綴：以原串串尾為自身串尾的子串，如 的後綴有：
注意：字元串前後綴都不包括該串本身
給你一個文本串T(Text String)
再給你一個模式串P(Pattern String)
問該模式串是否在文本串中，怎麼找？
一開始只好分別從文本串與模式串的串頭開始逐字母比較
二者相同，再比較T串與P串的下一位
如此反復
如果一直這么順利，兩串對應位置的字元總相同，待P串中最後一個字元也匹配完畢，說明該模式串在文本串中存在，耶( •̀ ω •́ )y超開心，查找結束。但，大多數匹配過程不會如此順利，在該例中，當匹配進行至
很明顯，失配了。現在怎麼辦？按樸素思想，將P串相對T串整體右移一位，重新開始匹配，即
但這種演算法效率無疑是十分低下的。設T串長度N，P串長度M，則樸素演算法時間復雜度為O(MN)
已知的重要信息並沒有被使用——已匹配的字元串前綴
在上例中，當P串最後一個字元匹配失敗時，其已有包含七個字元的 前綴子串S 匹配成功
完全可以利用前綴子串S做點什麼。觀察到在S串
中，有相同前後綴，即下圖藍色部分
而S串各字元又與T串中對應字元相同，即有
當失配發生後，直接將P串右移四位使S串藍色後綴部分對齊T串中藍色前綴部分
從圖中紅框部分繼續嘗試匹配，發現再次失配。這次，已匹配成功的前綴串S為
而在該串中沒有相同的前後綴，只能將P串串頭移至失配處進行比較
再次失配。此時前綴串S為空串，只好如樸素演算法般將P串整體右移一位，重新開始比較
匹配成功。於是又按照之前的步驟往下匹配，直至再次失配或匹配成功
後續步驟同上，不再贅述
上述示例已展現，KMP演算法的精髓在於對已匹配成功的前綴串S的利用
在樸素演算法中，匹配失敗了，T串待匹配字元會回溯
T串原本已匹配至T[7] = 'X'，但是因為失配，需回溯到T[1] = 'b'重新開始匹配
而在KMP演算法中，若P[M]與T[K]匹配失敗，K不會回溯。既然匹配過程是從T[0]開始逐漸向右進行的，至T[K]失配發生時，T[0]至T[K-1]早已匹配過，何必再回溯過去重復匹配呢？於是乎，就如問題引入部分展示般
每當失配發生，我們總是去關注P串中已匹配成功的前綴串S
因為該前綴串是匹配成功的，說明在T串中必定存在與該前綴串相同的子串，記為S'
若S串中存在相同前後綴
則S'串必然也存在此相同前後綴
所以只需將P串右移四位，使得S串的該相同前綴對齊S'串的該相同後綴
再嘗試比較T[7]與P[3]
至於T[7]與P[3]是否能夠匹配另說（當然，本例中一看就知道沒匹配上），但通過對前綴串S的利用，成功省去了P串右移一位、兩位和三位後的無效匹配
繼續深入思考，給定一個具體的P串，其第N位的前綴串S內容是固定的，則S是否存在相同前後綴、相同前後綴的長度與內容也是確定的。換言之，對於一個具體的P串，當其與給定T串匹配至P[N]失配，P串應右移幾位再次與T串進行匹配也是確定的。我們完全可以使用一個數組記錄當P[N]失配後，應當使用N之前的哪一位再來與T串進行匹配，以此提高匹配效率，記該數組為Next數組
定義Next[i] = j表示當P串中第i位失配後，跳轉至P串第j位再次嘗試匹配
還是以之前的P串為例，它的Next數組求出來應為
取下標5為例，其前綴串為
最長相同前後綴為
若P[5]失配，應跳轉至P[1]再次嘗試匹配（最長相同前綴對應P[0]，則取其後一位P[1]，若存在多位，則取最後一位的下一位），P[5]的前一個字元P[4]對應字元'a'，而P[1]前一個字元P[0]同對應字元'a'，保證了P[1]之前字元與T串中對應字元保持匹配。所以Next[5] = 1，其餘下標對應Next數組值同如此求。
特別地，規定Next[0] = -1。而對於除下標0外的任意下標N，Next[N]的含義是 前N-1個已匹配成功的字元構成的前綴串S中，最長相同前後綴長度。 所以若在下標為N處匹配失敗了，則應前往Next[N]所對應的下標處匹配。
具體地，以下圖所示為例，P[6]與T[6]失配
而Next[6] = 2，所以使用P[2]再次嘗試與T[6]進行匹配
當求出P串Next數組後，便可快速進行與T串的匹配
現在問題只剩下如何求Next數組，注意到Next數組既然只與P串本身相關，與文本串T無關，故令P串與自身匹配即可求得
考慮字元串
其Next數組應為
令其與給定文本串相匹配
當匹配進行至
失配，於是跳轉至P[Next[3]] = P[1]處再次嘗試匹配
再度失配，也必然失配
問題在於不該出現P[N] =P[Next[N]]
若P[N] =P[Next[N]]，則P[N]失配後使用P[Next[N]]再次嘗試匹配，由於P[N] =P[Next[N]]，P[N]匹配失敗，P[Next[N]]必然也失敗
因此，若出現P[N] =P[Next[N]]情況，則令Next[N]=Next[Next[N]]
本例中該字元串新Next數組為
當匹配進行至
失配，於是跳轉至P[Next[3]] = P[0]處再次嘗試匹配
省去了之前跳轉至P[1]處的無效匹配
設T串長度M，P串長度N，由於KMP演算法不會回溯，分析易知時間復雜度為O(m+n)
對於P[N]，若其前綴串S含相同前後綴F，且F長度為n（n>1），Next[N]可以取1至n中任意值，為最大化匹配效率考慮，總是取最大相同前後綴以提高效率，節省時間
⑵ 數據結構-串的模式匹配
串的模式匹配就是子串定位操作。給定兩明虧個串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分別是串s和t的長度），在主串s中尋找子串t的過程稱為模式匹配，t稱為模式。如果在s中找到等於t的子串，則稱匹配成功，返回t在s中的首次出現的下標位置；否則匹配失敗，返回-1。
本文介紹三個串模式匹配演算法，分別是簡單回溯演算法（Brute-Force，BF演算法）、KMP演算法、KMP演算法的改進。
從主串s的第0個字元開始，與模式串t的第0個字元開始逐字元比較，不相同時回溯到模式串t的第0個和主串s的第1個字元，重新開始比較。以此類推，直到t的所有字元完成匹配，則匹配成功，否則匹配失敗。
BF演算法速度慢的原因是存在大量不必要的回溯，即在某一趟與t的匹配過程失敗後，需要返回s串開始字元的下一字元重新開始比較，這對於某些模式串t來說是不必要的。例如，若s=12123123132，t=12313，在t與12 12312 3132中加粗子序列進行比較時，在 2 處發生失配，BF演算法接下來將t與121 23123 132、1212 31231 32、12123 12313 2比較。由於t中的231、312與其開始的123並不相同，顯然t與121 23123 132、1212 31231 32的比較是不必要的。
KMP演算法就是利用模式串中與模式串開頭部分子串的重復性來減少重復回溯，實現新一輪比較的直接跳轉。 具體來說，KMP演算法利用一個數組記錄模式串中每一個字元前面有幾個字元與模式串從頭重復，在與s串比較失配時，直接跳轉到重復子串的下一個字元繼續比較，而不用跳轉至模式串t的第0個字元。
演算法步驟： ①計算跳轉數組next。②利用KMP演算法進行模式匹配。
next數組通過遞推計算，即如果當前字元 t[j] 的前一個字元 t[j-1] 與其 next[j-1] 指向的字元 t[next[j-1]] 相同，意味著 t[j] 前的 next[j-1]+1 個字元與從 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，則遞推至 t[next[j-1]] 的next值指向的字元，與 t[j-1] 比較，直到確認 t[j] 前與 t 串從頭重復的數羨字元數，或者無重復字元標記為薯槐拍 0 。
注意此處的函數返回參數類型為int*，用於 返回一位數組 ，且返回的這個一位數組必須在函數中用static定義。
KMP演算法進行模式匹配時，只需在回溯時將 j 指針賦值為 next[j] 。需要注意的是，若 next[j] 為 -1 ，則意味著 t[j] 前面沒有與 t 從頭重復的字元，且 t[j] 與 s[i] 失配，則 i 和 j 均加 1 。
考慮更特殊的模式串，還能進一步減少不必要的回溯次數。例如，s=111211112，t=11112，按照上述next的計算方式，next={-1,0,1,2,3}。當 i=3, j=3 時失配，此時 s[i]=2, t[j]=1 ，由於 next[j]=2 ，於是 j 跳轉為 2 ，t=11 1 12與s=111 2 11112比較。由於 t[next[j]]=t[j] 也為 1 ，必然與 s[i]=2 不相同，顯然這次回溯也不必要。
總結來說， 當失配的字元與待跳轉的字元相同時，跳轉一步並無意義，可再跳一步 ，即將當前字元置為跳轉後字元的next值。
⑶ 數據結構 5.7 KMP演算法匹配過程
void get_nextval(char T[] int next[]){ //求模式串T的next函數值凳此並存入數組next j = ; next[ ] = ; k = ; while ( T[j+ ] != ) { if (k = = || T[j] = = T[k]) { ++j; ++k;羨粗山 if (T[j]!=T[k]) next[j] = k; else next[j] = next[k]; }//if else k = next[k]; }// while兄中}//get_nextval
KMP演算法匹配的過程動畫演示
lishixin/Article/program/sjjg/201311/23526
⑷ kmp演算法詳解
KMP模式匹配演算法
KMP演算法是一種改進的字元串匹配演算法,其關鍵是利用匹配失敗後的信息,盡量減少模式串與主串的匹配次數以達到快速匹配的目的明[4]。
求得模式的特徵向量之後，基於特徵分析的快速模式匹配演算法(KMP模式匹配演算法)與樸素匹配演算法類似，只是在每次匹配過程中發生某次失配時，不再單純地把模式後移一位，而是根據當前字元的特徵數來決定模式右移的位數[3]。
include "string. h"
#include<assert. h>
int KMPStrMatching(String T, String P, int. N, int startIndex)
{int lastIndex=T.strlen() -P.strlen();
if((1 astIndex- startIndex)<0)//若 startIndex過大,則無法匹配成功
return (-1);//指向P內部字元的游標
int i;//指向T內部字元的游標
int j=0;//指向P內部字元的游標
for(i= startIndex; i <T.strlen(); i++)
{while(P[j]!=T[i]&& j>0)
j=N[j-1];
if(P[j]==T[i])
j++;
if(j ==P.strlen())
return(1-j+1);//匹配成功,返回該T子串的開始位置
}
return (-1);
}
⑸ kmpe演算法詳解
KMP演算法是拿來處理字元串匹配的。換句話說，給你兩個字元串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字元串A="I"m matrix67"，字元串B="matrix"，我們就說B是A的子串。
解決這類問題，通常我們的方法是枚舉從A串的什麼位置起開始與B匹配，然後驗證是否匹配。假如A串長度為n，B串長度為m，那麼這種方法的復雜度是O (mn)的。雖然很多時候復雜度達不到mn（驗證時只看頭一兩個字母就發現不匹配了），但我們有許多「最壞情況」，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我們將介紹的是一種最壞情況下O(n)的演算法（這里假設 m<=n），即傳說中的KMP演算法。
望採納 謝謝
⑹ 演算法基礎 - 樸素模式匹配演算法、KMP模式匹配演算法
假設我們要從 主字元串goodgoogle 中匹配 子字元串google
樸素模式匹配演算法就是 通過從主字元的頭部開始 一次循環匹配的字元串的挨個字元 如果不通過 則主字元串頭部位置遍歷位置+1 在依次遍歷子字元串的字元
匹配過程
主字元串從第一位開始 取出g 子字元串取出第一位 g 匹配 進入子循環
取出o 取出o 匹配
取出o 取出o 匹配
取出d 取出g 不匹配 主字元串遍歷位置+1
主字元串從第二位開始 取出o 子字元串取出第一位 g 不匹配 主字元串遍歷位置+1
主字元串從第三位開始 取出o 子字元串取出第一位 g 不匹配 主字元串遍歷位置+1
主字元串從第四位開始 取出d 子字元串取出第一位 g 不匹配 主字元串遍歷位置+1
主字元串從第五位開始 取出g 子字元串取出第一位 g 匹配 進入子循環
取出o 取出o 匹配
取出o 取出o 匹配
取出g 取出g 匹配
取出l 取出l 匹配
取出e 取出e 匹配 子循環結束 匹配成功
假設主字元串 長度為 n 子字元串長度為m n>= m
最好的情況需要匹配m次 時間復雜度為 0(m)
例如 000000000001 匹配 00001 每次進入子循環之後 都要遍歷到最後一次子循環才得出不匹配
需要匹配次數 (n-m+1) * m
最壞的情況需要匹配m次 時間復雜度為 0((n-m+1) * m)
KMP 演算法的主要核心就是 子字元串在子循環內得出不匹配時 主字元串當前的判斷位不需要回溯–也就是不可以變小 ，且子循環的判斷位需要回溯 回溯位與子字元串本身是否具有重復結構有關 。 以此來規避無效的判斷
時間復雜度為 O(n+m)
如果主串 S = "abcdefgab" 我們要匹配的子串 T = "abcdex" 如果用前面的樸素演算法 ， 前5個字母完全相同
直到第6個字母 f 和 x 不同
步驟1
S: a b c d e f g a b
T: a b c d e x
接下來如果用樸素演算法的話 那麼應該是如下比較
步驟2
S: a b c d e f g a b
T: # a b c d e x
b 和 a 不匹配
步驟3
S: a b c d e f g a b
T: # # a b c d e x
a和c 不匹配
步驟4
S: a b c d e f g a b
T: # # # # a b c d e x
d和a 不匹配
步驟5
S: a b c d e f g a b
T: # # # # a b c d e x
a和e 不匹配
步驟6
S: a b c d e f g a b
T: # # # # # a b c d e x
即主串S中的第2 ，3 ， 4， 5， 6 位都與子串T的首字元不相等
對於子串T來說 如果首字元a與後面的bcdex中任意一個字元都不相等
那麼對於上面的第一步來說 前五位都相等 那麼 可以得到 子串首字元a 與主串的第2，3，4，5 位都不相等
即步驟2 ， 3 ，4 ，5 都是多餘的 可以直接進入步驟6
如果子串的首字元串與後面的字元有相等的情況
假設S = "abcababca" T= "abcabx"
樸素演算法
步驟1
S: a b c a b a b c a
T: a b c a b x
a 與 x 不匹配
步驟2
S: a b c a b a b c a
T: # a b c a b x
b 與 a 不匹配
步驟3
S: a b c a b a b c a
T: # # a b c a b x
c 與 a 不匹配
步驟4
S: a b c a b a b c a
T: # # # a b c a b x
a 與 a 匹配
步驟5
S: a b c a b a b c a
T: # # # # a b c a b x
b 與 b 匹配
步驟6
S: a b c a b a b c a
T: # # # # a b c a b x
a 與 c 不匹配
因為步驟1 中已經得出 前五位已經完全匹配 並且子串首字元ab 存在相同的情況 所以 步驟2，3 是多餘的
直接進入步驟4 因為步驟1中已經得出 主串與子串前五位相同 同時 子串1 2 位與 子串的4 5 位相同 所以可得出
子串1 2 位 與當前主串匹配位置開始的前兩位也就是主串的4 5 位匹配 所以步驟4 , 5 是多餘的 可以直接進入步驟6
通過上面的兩個例子我們可以發現 主串的比較位是不會回溯的 ， 而子串的比較位與子串本身結構中是否有重復相關
子串不重復 舉例
S: a b c d e f g a
T: a b c d e x
子串第6位不匹配 且本身沒有重復 那麼下一次循環 就變成了 子串的第一位與主串的第二位比較
即子串的匹配位從6 變成了1
S: a b c d e f g a
T: # a b c d e x
子串重復 舉例
S: a b c a b a b c a
T: a b c a b x
a 與 x 不匹配
子串在第六位發生不匹配是 前五位abcab 具有重復結構 ab 所以子串匹配位發生變化 即子串的匹配位從6 變成了 3
S: a b c a b a b c a
T: # # # a b c a b x
a 與 c 不匹配
我們可以得出 子串匹配位的值 與主串無關 只取決於當前字元串之前的串前後綴的相似度
也就是說 我們在查找字元前 ，要先對子串做一個分析 獲取各個位置不匹配時 下一步子串的匹配位
前綴 ： 從頭開始數 不包含最後一位
後綴 : 不是倒著數 是以和前綴相同的字元串為結尾的部分
例如 字元串 a 沒有前後綴
字元串 ab 沒有前後綴
字元串 aba 沒有前後綴
字元串 abab 前後綴 ab
字元串 ababa 前後綴 可以是 a 可以是 aba 我們取長度最長的 即 aba
第一位時 next值固定為0
其他情況 取其公共最長前後綴的長度+1 沒有則為1
因為一共子串有8位 所以在子循環內一共需要獲取 8次前後綴
這里我們定義一個next數組 長度為8 裡面的元素分別對應子串各個子循環內的 前後綴長度
第1位不匹配時 獲取字元串為a 沒有前字元串 沒有前後綴 那麼next[1] = 0
第2位不匹配時 獲取字元串為ab 有前字元串a 沒有前後綴 那麼next[2] = 1
第3位不匹配時 獲取字元串為aba 有前字元串ab 沒有前後綴 那麼next[3] = 1
第4位不匹配時 獲取字元串為abab 有前字元串aba 前後綴 a 那麼next[4] = 2
第5位不匹配時 獲取字元串為ababa 有前字元串abab 前後綴 ab 那麼next[5] = 3
第6位不匹配時 獲取字元串為ababaa 有前字元串ababa 前後綴 aba 那麼next[6] = 4
第7位不匹配時 獲取字元串為ababaab 有前字元串ababaa 前後綴 a 那麼next[7] = 2
第8位不匹配時 獲取字元串為ababaabc 有前字元串ababaab 前後綴 ab 那麼next[8] = 3
next數組為[ 0, 1 , 1 ,2 , 3, 4 ,2, 3 ]
後來有人發現 KMP還是有缺陷的 比如 當子串 T = "aaaaax"
在5位發生不匹配 此時 next[5] = 4 接著就是 子串中的第四位a與 主串當前位置字元比較
因為子串第五位等於子串第四位相同 所以可以得出該步驟也不匹配 此時 next[4] = 3
依然不匹配 直到next[1] = 0
我們可以發現由於T串中的 2 3 4 5 位置都與首位a 相等 中間的過程都是多餘的
那麼可以用首位的next[1] 的值 去替代與它相等的字元後續的next[x]的值
⑺ kmp演算法什麼意思
1.KMP演算法是一種改進的字元串匹配演算法，由克努特，莫里斯和普拉特同時發現，因此人們稱它為克努特·莫里斯·普拉特操作，簡稱KMP演算法；
2.KMP演算法喊掘的關鍵是利用匹配失高歷敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現戚滲搜就是實現一個next函數，函數本身包含了模式串的局部匹配信息；
3.在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。
⑻ 沒有使用貪心策略的演算法
KMP演算法。
KMP演算法是一種改進的字元串匹配演算法。為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]數組，next[j]的值表示P[0...j-1]中最長後綴的長度等於相同字元序列的前綴，在中逗緩匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配指睜；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。
貪心演算法，又稱貪婪演算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，演算法得到的賣模是在某種意義上的局部最優解。
⑼ 圖解KMP字元串匹配演算法
kmp演算法跟之前講的bm演算法思想有一定的相似性。之前提到過，bm演算法中有個好後綴的概念，而在kmp中有個好前綴的概念，什麼是好前綴，我們先來看下面這個例子。
觀察上面這個例子，已經匹配的abcde稱為好前綴，a與之後的bcde都不匹配，所以沒有必要再比一次，直接滑動到e之後即可。
那如果前綴中有互相匹配的字元呢？
觀察上面這個例子，這個時候如果我們直接滑到好前綴之後，則會過度滑動，錯失匹配子串。那我們如何根據好前綴來進行合理滑動？
其實就是看當前的好前綴的前綴和後綴是否有匹配的，找到最長匹配長度，直接滑動。鑒於不止一次找最長匹配長度，我們完全可以先初始化一個數組，保存在當前好前綴情況下，最長匹配長度是多少，這時候我們的next數組就出來了。
我們定義一個next數組，表示在當前好前綴下，好前綴的前綴和後綴的最長匹配子串長度，這個最長匹配長度表示這個子串之前已經匹配過匹配了，不需要再次進行匹配，直接從子串的下一個字元開始匹配。
我們是否每次算next[i]時都需要每一個字元進行匹配，是否可以根據next[i - 1]進行推導以便減少不必要的比較。
帶著這個思路我們來看看下面的步驟：
假設next[i - 1] = k - 1;
如果modelStr[k] = modelStr[i] 則next[i]=k
如果modelStr[k] != modelStr[i]，我們是否可以直接認定next[i] = next[i - 1]？
通過上面這個例子，我們可以很清晰地看到，next[i]!=next[i-1]，那當modelStr[k]!=modelStr[i]時候，我們已知next[0],next[1]…next[i-1]，如何推導出next[i]呢？
假設modelStr[x…i]是前綴後綴能匹配的最長後綴子串，那麼最長匹配前綴子串為modelStr[0…i-x]
我們在求這個最長匹配串的時候，他的前面的次長匹配串（不包含當前i的），也就是modelStr[x…i-1]在之前應該是已經求解出來了的，因此我們只需要找到這個某一個已經求解的匹配串，假設前綴子串為modelStr[0…i-x-1],後綴子串為modelStr[x…i-1],且modelStr[i-x] == modelStr[i],這個前綴後綴子串即為次前綴子串，加上當前字元即為最長匹配前綴後綴子串。
代碼實現
首先在kmp演算法中最主要的next數組，這個數組標志著截止到當前下標的最長前綴後綴匹配子串字元個數，kmp演算法裡面，如果某個前綴是好前綴，即與模式串前綴匹配，我們就可以利用一定的技巧不止向前滑動一個字元，具體看前面的講解。我們提前不知道哪些是好前綴，並且匹配過程不止一次，因此我們在最開始調用一個初始化方法，初始化next數組。
1.如果上一個字元的最長前綴子串的下一個字元==當前字元，上一個字元的最長前綴子串直接加上當前字元即可
2.如果不等於，需要找到之前存在的最長前綴子串的下一個字元等於當前子串的，然後設置當前字元子串的最長前綴後綴子串
然後開始利用next數組進行匹配，從第一個字元開始匹配進行匹配，找到第一個不匹配的字元，這時候之前的都是匹配的，接下來先判斷是否已經是完全匹配，是直接返回，不是，判斷是否第一個就不匹配，是直接往後面匹配。如果有好前綴，這時候就利用到了next數組，通過next數組知道當前可以從哪個開始匹配，之前的都不用進行匹配。
⑽ kmp演算法什麼意思
KMP演算法之所以叫做KMP演算法是因為這個演算法是由三個人共同提出來的，就取三個人名字的首字母作為該演算法的名字。其實KMP演算法與BF演算法的區別就在於KMP演算法巧妙的消除了指針i的回溯問題，只需確定下次匹配j的位置即可，使得問題的復雜度由O(mn)下降到O(m+n)。
在KMP演算法中，為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]數組，next[j]的值表示P[0...j-1]中最長後綴的長度等於相同字元序列的前綴。
對於next[]數組的定義如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0時，表示P[0...k-1]=P[j-k,j-1]
因此KMP演算法的思想就是：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。