kmp匹配演算法java

『壹』 圖解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數組知道當前可以從哪個開始匹配，之前的都不用進行匹配。

『貳』 java編程實現字元串的模式匹配

傳統的字元串模式匹配演算法（也就是BF演算法）就是對於主串和模式串雙雙自左向右，一個一個字元比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的演算法時間復雜度為O（n＊m），其中n和m分別為串s和串t的長度。

KMP 演算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt演算法，簡稱KMP演算法。KMP演算法是字元串模式匹配中的經典演算法。和BF演算法相比，KMP演算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結果使得演算法時間復雜度只為O（n＋m）。

『叄』 字元串匹配演算法的使用（未完待整理）

字元串的匹配在Java中都知道使用indexOf函數來實現，那麼其匹配演算法是怎麼樣的呢？

單模式和多模式的區別就是一次遍歷主串能否將多個模式的字元串都查找出來。

英文全稱為Brute Force，暴力匹配演算法，匹配字元串的方法比較暴力，也比較簡單易懂。其大概的思路就是：

我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那麼總共需要尋找(n-m+1)次，且每次都需要比對m次，那麼時間復雜度將是 (n-m+1)*m ，即 O(n*m) ；但實際上並不會這么低效，因為我們的使用場景中主串和模式串都不會太長，而且在每個子串和模式串進行比對時，只要中途有一個不匹配，那麼當前比對就會提前結束，因此大部分情況下，時間復雜度都會比 O(n*m) 要好。

我們在BF演算法的基礎上引入哈希演算法，我們不需要將每個子串與模式串逐個字元地進行比較，而是計算得出每個子串的hash值，然後和模式串的hash值進行比較，如果有相等的，那就說明有子串和模式串匹配上了。

雖然我們只需要比對模式串和子串的hash值就能得到匹配結果，次數為(n-m+1)，但是對每個子串進行hash計算的時候，是要遍歷每個字元的，因此次數也是m，那麼總的時間復雜度還是 O(n*m) ，並沒有明顯地提升。

那麼我們該如何想出一個辦法，使得每個子串hash值的計算時間得到提升呢？這就是RK演算法的精髓，假設子串包含的字元集中元素個數為k，那麼就用k進制數來代表這個子串，然後hash的過程就是將這個k進制的數轉換為十進制的數，這個十進制的數就是該子串的hash值。

相鄰子串的hash值計算是有規律的，我們只需要遍歷一次主串就能得到所有子串的hash值，演算法復雜度為O(n)，而不是像原先一樣，每個子串都需要O(m)的時間復雜度。

然後將模式串的hash值和所有子串的hash值進行比較，每次比較的時間復雜度是 O(1) ，總共比較(n-m+1)次，所以RK演算法的總的時間開銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時間復雜度比BF演算法更加高效。

當然，有hash的地方就有可能會存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內容就是不一樣，此時怎麼辦呢？其實很簡單，對於hash值一樣的子串，我們增加雙保險，再比較一下這m個字元是否都一樣即可，總的時間開銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。

如果極端情況下出現了很多hash沖突呢？我們對於每個和模式串相同hash值的子串都需要逐一再進行比較，那麼總的時間開銷就會為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過這種概率太小了，大部分情況下都不會這樣。

在真正的文本編輯器中查找和替換某個字元串時，使用的演算法既不是上述的BF演算法，也不是RK演算法；BF演算法只適合不是很長的主串，RK演算法則要設計一個沖突概率很低的hash演算法，這個比較困難，所以實際使用的是BM演算法，它是工程中非常常用的一種字元串匹配演算法，效率也是最高的。

演算法的思想和過程有些復雜，待以後整理。

KMP演算法在本質上是和BM演算法一樣的。演算法的思想和過程有些復雜，待以後整理。

瀏覽器輸入框中的智能輸入匹配是怎麼實現的，它是怎麼做動態字元串匹配查找的呢？這就用到了Trie樹。

又名字典樹，是一種專門用來快速查找字元串前綴匹配結果的樹形結構，其本質就是將所有字元串的重復的前綴合並在一起，構造一個多叉樹。

其中，根節點不包含任何信息，每個節點表示一個字元，從根節點到紅色節點的一條路徑表示存儲的一個字元串。當我們在如上Trie樹中查找"he"時，發現"he"並非是一個字元串，而是"hello"和"her"的公共前綴，那麼就會找到這兩個字元串返回。

Trie樹在內存中是如何存儲的呢？因為每一個節點都可能是包含所有字元的，所以每一個節點都是一個數組（或者散列表），用來存儲每個字元及其後綴節點的指針。

使用Trie樹，最開始構建的時候，時間復雜度為 O(n) ，其中n為所有字元串長度之和，但是一旦構建完成，頻繁地查詢某個字元串是非常高效的，時間復雜度為 O(k) ，其中k為查找字元串的長度。

Trie樹雖然查詢效率很高，但是比較浪費內存，每一個節點都必須維護一個數組存放所有可能的字元數據及其指向下一個節點的指針，因此在所有字元串公共前綴並不多的時候，內存空間浪費地就更多了。這種問題其實也有對應的解決辦法，我們可以不使用數組，而是使用有序數組、散列表、紅黑樹來存放，可以相應地降低性能來節省內存空間。

Trie樹除了可以實現瀏覽器動態輸入內容查找候選項的功能外，還可以實現多模式地敏感詞匹配功能。假設我們需要對用戶輸入的內容進行敏感詞檢查，將所有的敏感內容用***代替，那麼該如何實現呢？

首先我們可以維護一個敏感詞字典，使用上述四種單模式匹配演算法也可以實現，但是需要遍歷N次用戶輸入的內容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們如果將敏感詞字典維護為一個Trie樹，然後將用戶輸入的內容從位置0開始在Trie樹中進行查詢，如果匹配到紅色節點，那麼說明有敏感詞；如果沒有匹配到紅色節點，就從用戶輸入內容的下一個位置開始繼續在Trie樹中查詢，直至將用戶輸入內容遍歷完，因此我們只是遍歷了一遍主串。

然而更高效的多模式字元串匹配使用地更多的是如下的AC自動機。

如果把Trie樹比作BF演算法，KMP演算法是BF演算法的改進，那麼AC自動機就是利用同樣的思想改進了Trie樹。

演算法的思想和過程有些復雜，待以後整理。

『肆』 串的應用kmp演算法。求一個字元串在另一個字元串中第一次出現的位置。

KMP.java

源代碼為：

package algorithm.kmp;

/**
* KMP演算法的Java實現例子與測試、分析
* @author 崔衛兵
* @date 2009-3-25
*/
public class KMP {
/**
* 對子串加以預處理，從而找到匹配失敗時子串回退的位置
* 找到匹配失敗時的最合適的回退位置，而不是回退到子串的第一個字元，即可提高查找的效率
* 因此為了找到這個合適的位置，先對子串預處理，從而得到一個回退位置的數組
* @param B，待查找子串的char數組
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循環一次，就會找到一個回退位置
for(int i=1;i<size;i++){
//當找到第一個匹配的字元時，即j>0時才會執行這個循環
//或者說p2中的j++會在p1之前執行（限於第一次執行的條件下）
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有當子串中含有重復字元時，回退的位置才會被優化
if(B[j]==B[i]){
j++;
}
//找到一個回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}

/**
* KMP實現
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//當找到第一個匹配的字元時，即j>0時才會執行這個循環
//或者說p2中的j++會在p1之前執行（限於第一次執行的條件下）
//p1
while(j>0 && B[j]!=A[i]){
//找到合適的回退位置
j=P[j-1];
}
//p2 找到一個匹配的字元
if(B[j]==A[i]){
j++;
}
//輸出匹配結果，並且讓比較繼續下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}

public static void main(String[] args) {
//回退位置數組為P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!這個會匹配1次","abcdef");
//回退位置數組為P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!這個會匹配2次","ititit");
//回退位置數組為P[0, 0, 0]
kmp("測試漢字的匹配，崔衛兵。這個會匹配1次","崔衛兵");
//回退位置數組為P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("這個會匹配0次","it1it1it1");
}
}

『伍』 KMP模式匹配演算法是什麼

KMP模式匹配演算法是一種改進演算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出來的，因此人們稱它為「克努特－莫里斯－普拉特操作」，簡稱KMP演算法。此演算法可以在O（n＋m）的時間數量級上完成串的模式匹配操作。其改進在於：每當一趟匹配過程出現字元不相等時，主串指針i不用回溯，而是利用已經得到的「部分匹配」結果，將模式串的指針j向右「滑動」盡可能遠的一段距離後，繼續進行比較。

1.KMP模式匹配演算法分析回顧圖4－5所示的匹配過程示例，在第三趟匹配中，當i＝7、j＝5字元比較不等時，又從i＝4、j＝1重新開始比較。然而，經仔細觀察發現，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1這三次比較都是不必進行的。因為從第三趟部分匹配的結果就可得出，主串中的第4、5和6個字元必然是b、c和a（即模式串第2、第2和第4個字元）。因為模式中的第一個字元是a，因此它無須再和這三個字元進行比較，而僅需將模式向右滑動2個字元的位置進行i＝7、j＝2時的字元比較即可。同理，在第一趟匹配中出現字元不等時，僅需將模式串向右移動兩個字元的位置繼續進行i＝2、j＝1時的字元比較。由此，在整個匹配過程中，i指針沒有回溯，如圖1所示。

圖1改進演算法的模式匹配過程示意

『陸』 【演算法筆記】字元串匹配

BF 演算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配演算法，也叫樸素匹配演算法：

主串和模式串：
在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m

我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。

BF 演算法的時間復雜度是 O(n*m)

等價於

比如匹配Google 和Goo 是最好時間復雜度，匹配Google 和ble是匹配失敗的最好時間復雜度。

KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth與J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特—莫里斯—普拉特演算法。KMP演算法主要分為兩個步驟：字元串的自我匹配，目標串和模式串之間的匹配。

看來網上很多的文章，感覺很多的都沒有說清楚，這里直接復制阮一峰的內容，講的很清晰
內容來自 http://www.ruanyifeng.com/blog/

首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜索詞"ABCDABD"的第一個字元，進行比較。因為B與A不匹配，所以搜索詞後移一位。

因為B與A不匹配，搜索詞再往後移。

就這樣，直到字元串有一個字元，與搜索詞的第一個字元相同為止。

接著比較字元串和搜索詞的下一個字元，還是相同。

直到字元串有一個字元，與搜索詞對應的字元不相同為止。

這時，最自然的反應是，將搜索詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經比較過的位置，重比一遍。

一個基本事實是，當空格與D不匹配時，你其實知道前面六個字元是"ABCDAB"。KMP演算法的想法是，設法利用這個已知信息，不要把"搜索位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。

怎麼做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，後面再介紹，這里只要會用就可以了。

已知空格與D不匹配時，前面六個字元"ABCDAB"是匹配的。查表可知，最後一個匹配字元B對應的"部分匹配值"為2，因此按照下面的公式算出向後移動的位數：

因為 6 - 2 等於4，所以將搜索詞向後移動4位。

因為空格與C不匹配，搜索詞還要繼續往後移。這時，已匹配的字元數為2（"AB"），對應的"部分匹配值"為0。所以，移動位數 = 2 - 0，結果為 2，於是將搜索詞向後移2位。

因為空格與A不匹配，繼續後移一位。

逐位比較，直到發現C與D不匹配。於是，移動位數 = 6 - 2，繼續將搜索詞向後移動4位。

逐位比較，直到搜索詞的最後一位，發現完全匹配，於是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數 = 7 - 0，再將搜索詞向後移動7位，這里就不再重復了。

下面介紹《部分匹配表》是如何產生的。

首先，要了解兩個概念："前綴"和"後綴"。 "前綴"指除了最後一個字元以外，一個字元串的全部頭部組合；"後綴"指除了第一個字元以外，一個字元串的全部尾部組合。

"部分匹配值"就是"前綴"和"後綴"的最長的共有元素的長度。以"ABCDABD"為例，

"部分匹配"的實質是，有時候，字元串頭部和尾部會有重復。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分匹配值），就可以來到第二個"AB"的位置。

BM（Boyer-Moore）演算法。它是一種非常高效的字元串匹配演算法，有實驗統計，它的性能是著名的KMP 演算法的 3 到 4 倍。

BM 演算法包含兩部分，分別是壞字元規則（bad character rule）和好後綴規則（good suffix shift）

未完待續

參考文章：
字元串匹配的Boyer-Moore演算法

『柒』 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);

}

『捌』 數據結構與演算法——字元串匹配問題(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種情況