字元串kmp演算法
㈠ 數據結構與演算法——字元串匹配問題(KMP演算法)
KMP演算法也是比較著名的模式匹配演算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 發表的一個模式匹配演算法。可以大大避免重復遍歷的情況。
如果使用暴風演算法的話，前面五個字母完全相等，直到第六個字母 "f" 和 "x" 不相等。如下圖：
T = 「abcdex」
j 123456
模式串 abcdex
next[j] 011111
T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123
T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223
T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678
next數組其實就是求解字元串要回溯的位置
假設，主串S= 「abcababca」;模式串T=「abcdex」，由以上分析得出next數組為011111，next數組意味著當主串與模式串不匹配時，都需要從第一個的位置重新比較。
KMP演算法也是有缺陷的，比如主串S=「aaaabcde」,模式串T= 「aaaaax」。next的數組就是012345；
當開始匹配時，當i= 5，j = 5時，我們發現字元"b"與字元「a」不相等，如上圖，j = next[5] = 4;
由於T串的第二、三、四、五位置的字元都與首位「a」相等，那麼可以用首位next[1]的值去取代與它相等的後續字元的next[j],那麼next數組為{0,0,0,0,0,5};
在求解nextVal數組的5種情況
㈡ 演算法-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中任意值，為最大化匹配效率考慮，總是取最大相同前後綴以提高效率，節省時間
㈢ 圖解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演算法求next數組的問題
字元串如果是以0為下標的話next[7]是0，只有最後一位與第一位相等。
在第i個字元前面的i-1個字元裡面，
從開頭開始的1個字元與最後1個字元是否相等，若不是，則next[i]=0；
從開頭開始的2個字元與最後2個字元是否相等，若不是，則next[i]=1；
從開頭開始的3個字元與最後3個字元是否相等，若不是，則next[i]=2；
前綴next數組的求解演算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字元串長度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推。
(4)字元串kmp演算法擴展閱讀：
kmp演算法完成的任務是：給定兩個字元串O和f，長度分別為n和m，判斷f是否在O中出現，如果出現則返回出現的位置。常規方法是遍歷a的每一個位置，然後從該位置開始和b進行匹配，但是這種方法的復雜度是O(nm)。kmp演算法通過一個O(m)的預處理，使匹配的復雜度降為O(n+m)。
㈤ 解析一哈c語言中的kmp演算法，bf演算法,kr演算法之間的聯系與區別，盡量淺顯易懂，謝謝！
三種演算法聯系：都是字元串匹配演算法。
區別：
「KMP演算法」：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。
「BF演算法」是普通的模式匹配演算法，BF演算法的思想就是將目標串S的第一個字元與模式串P的第一個字元進行匹配，若相等，則繼續比較S的第二個字元和P的第二個字元；若不相等，則比較S的第二個字元和P的第一個字元，依次比較下去，直到得出最後的匹配結果。
「KR演算法」在每次比較時，用HASH演算法計算文本串和模式串的HASH映射，通過比較映射值的大小來比較字元串是否匹配。但是考慮到HASH沖突，所以在映射值相同的時候，還需要近一步比較字元串是否相同。但是在每次比較時，需要計算HASH值，所以選擇合適的HASH演算法很重要。
略知一二！
㈥ kmp演算法的基本思想
主串：a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b，下文中我們稱作T
模式串：a
b
a
c
a
b，下文中我們稱作W
在暴力字元串匹配過程中，我們會從T[0]
跟
W[0]
匹配，如果相等則匹配下一個字元，直到出現不相等的情況，此時我們會簡單的丟棄前面的匹配信息，然後從T[1]
跟
W[0]匹配，循環進行，直到主串結束，或者出現匹配的情況。這種簡單的丟棄前面的匹配信息，造成了極大的浪費和低下的匹配效率。
然而，在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。
比如，在簡單的一次匹配失敗後，我們會想將模式串盡量的右移和主串進行匹配。右移的距離在KMP演算法中是如此計算的：在已經匹配的模式串子串中，找出最長的相同的前綴和後綴，然後移動使它們重疊。
在第一次匹配過程中
T:
a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
在T[5]與W[5]出現了不匹配，而T[0]~T[4]是匹配的，現在T[0]~T[4]就是上文中說的已經匹配的模式串子串，現在移動找出最長的相同的前綴和後綴並使他們重疊：
T:
a
b
a
c
aab
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
然後在從上次匹配失敗的地方進行匹配，這樣就減少了匹配次數，增加了效率。
然而，有些同學可能會問了，每次都要計算最長的相同的前綴會不會反而浪費了時間，對於模式串來說，我們會提前計算出每個匹配失敗的位置應該移動的距離，花費的時間是常數時間。比如：
j012345W[j]abacabF(j)001012當W[j]與T[i]不匹配的時候，設置j
=
F(j-1)
文獻中，朱洪對KMP演算法作了修改，他修改了KMP演算法中的next函數，即求next函數時不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他記修改後的next函數為newnext。顯然在模式串字元重復高的情況下，朱洪的KMP演算法比KMP演算法更加有效。
以下給出朱洪的改進KMP演算法和next函數和newnext函數的計算演算法。