字元串匹配演算法kmp遞歸實現

1. C語言如何實現KMP字元串匹配

#include <stdio.h>

#include <stdlib.h>

void KmpNextArray(const char* str, int len, int* next) {

/**/if (str == NULL || next == NULL || len <= 0) {

/**//**/return;

/**/}

/**/int n = 1;

/**/int i = 1;

/**/next[0] = 0;

/**/while (i < len && str[i] != str[0]) {

/**//**/next[i++] = 0;

/**/}

/**/if (i >= len) {

/**//**/return;

/**/}

/**/next[i++] = 1;

/**/for (; i < len; i++) {

/**//**/if (str[i] == str[n]) {

/**//**//**/next[i] = ++n;

/**//**/}

/**//**/else {

/**//**//**/next[i] = 0;

/**//**//**/n = 0;

/**//**/}

/**/}

}

int Strlen(const char* str) {

/**/if (str == NULL) {

/**//**/return 0;

/**/}

/**/int n = 0;

/**/while (str[n] != '') {

/**//**/++n;

/**/};

/**/return n;

}

const char* KmpFind(const char* str, const char* findstr) {

/**/if (NULL == str || NULL == findstr) {

/**//**/return NULL;

/**/}

/**/int slen = Strlen(str);

/**/if (0 == slen) {

/**//**/return NULL;

/**/}

/**/int flen = Strlen(findstr);

/**/if (0 == flen) {

/**//**/return NULL;

/**/}

/**/if (flen > slen) {

/**//**/return NULL;

/**/}

/**/int* next = (int*)malloc(sizeof(int) * flen);

/**/if (NULL == next) {

/**//**/return NULL;

/**/}

/**/KmpNextArray(findstr, flen, next);

/**/const char* p = str;

/**/int n = 0;

/**/while (p < str + slen) {

/**//**/if (findstr[n] == *p) {

/**//**//**/if (++n >= flen) {

/**//**//**//**/free((void*)next);

/**//**//**//**/return p - n + 1;

/**//**//**/}

/**//**//**/else {

/**//**//**//**/++p;

/**//**//**/}

/**//**/}

/**//**/else if (n > 0) {

/**//**//**/n = next[n - 1];

/**//**/}

/**//**/else {

/**//**//**/++p;

/**//**/}

/**/}

/**/free(next);

/**/return NULL;

}

int main(int argc, char* argv[]) {

/**/char a[100] = { 0 };

/**/char b[100] = { 0 };

/**/fgets(a, 100, stdin);

/**/fgets(b, 100, stdin);

/**///a b均帶有換行符

/**/int alen = Strlen(a) - 1;

/**/int blen = Strlen(b) - 1;

/**/a[alen] = '';

/**/b[blen] = '';

/**/const char* p = KmpFind(a, b);

/**/if (NULL != p) {

/**//**/printf("%s %8d ", a, alen);

/**//**/for (int i = 0; i < (int)(p - a); i++) {

/**//**//**/putchar(' ');

/**//**/}

/**//**/printf("%0.*s %*d ", blen, p, 8 + alen - (int)(p - a) - blen, (int)(p - a));

/**/}

/**/else {

/**//**/printf("No string found! ");

/**/}

/**/return 0;

}

運行截圖

2. 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，繼續進行比較。

3. 哭了~正在學數據結構中的 KMP 演算法

KMP演算法是拿來處理字元串匹配的。換句話說，給你兩個字元串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字元串A="I'm matrix67"，字元串B="matrix"，我們就說B是A的子串。你可以委婉地問你的MM：「假如你要向你喜歡的人表白的話，我的名字是你的告白語中的子串嗎？」
解決這類問題，通常我們的方法是枚舉從A串的什麼位置起開始與B匹配，然後驗證是否匹配。假如A串長度為n，B串長度為m，那麼這種方法的復雜度是O (mn)的。雖然很多時候復雜度達不到mn（驗證時只看頭一兩個字母就發現不匹配了），但我們有許多「最壞情況」，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我們將介紹的是一種最壞情況下O(n)的演算法（這里假設 m<=n），即傳說中的KMP演算法。
之所以叫做KMP，是因為這個演算法是由Knuth、Morris、Pratt三個提出來的，取了這三個人的名字的頭一個字母。這時，或許你突然明白了AVL 樹為什麼叫AVL，或者Bellman-Ford為什麼中間是一杠不是一個點。有時一個東西有七八個人研究過，那怎麼命名呢？通常這個東西乾脆就不用人名字命名了，免得發生爭議，比如「3x+1問題」。扯遠了。
個人認為KMP是最沒有必要講的東西，因為這個東西網上能找到很多資料。但網上的講法基本上都涉及到「移動(shift)」、「Next函數」等概念，這非常容易產生誤解（至少一年半前我看這些資料學習KMP時就沒搞清楚）。在這里，我換一種方法來解釋KMP演算法。

假如，A="abababaababacb"，B="ababacb"，我們來看看KMP是怎麼工作的。我們用兩個指針i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應地變化，且j滿足以A[i]結尾的長度為j的字元串正好匹配B串的前 j個字元（j當然越大越好），現在需要檢驗A[i+1]和B[j+1]的關系。當A[i+1]=B[j+1]時，i和j各加一；什麼時候j=m了，我們就說B是A的子串（B串已經整完了），並且可以根據這時的i值算出匹配的位置。當A[i+1]<>B[j+1]，KMP的策略是調整j的位置（減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續增加）。我們看一看當 i=j=5時的情況。

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

此時，A[6]<>B[6]。這表明，此時j不能等於5了，我們要把j改成比它小的值j'。j'可能是多少呢？仔細想一下，我們發現，j'必須要使得B[1..j]中的頭j'個字母和末j'個字母完全相等（這樣j變成了j'後才能繼續保持i和j的性質）。這個j'當然要越大越好。在這里，B [1..5]="ababa"，頭3個字母和末3個字母都是"aba"。而當新的j為3時，A[6]恰好和B[4]相等。於是，i變成了6，而j則變成了 4：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

從上面的這個例子，我們可以看到，新的j可以取多少與i無關，只與B串有關。我們完全可以預處理出這樣一個數組P[j]，表示當匹配到B數組的第j個字母而第j+1個字母不能匹配了時，新的j最大是多少。P[j]應該是所有滿足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
再後來，A[7]=B[5]，i和j又各增加1。這時，又出現了A[i+1]<>B[j+1]的情況：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

由於P[5]=3，因此新的j=3：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

這時，新的j=3仍然不能滿足A[i+1]=B[j+1]，此時我們再次減小j值，將j再次更新為P[3]：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

現在，i還是7，j已經變成1了。而此時A[8]居然仍然不等於B[j+1]。這樣，j必須減小到P[1]，即0：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7

終於，A[8]=B[1]，i變為8，j為1。事實上，有可能j到了0仍然不能滿足A[i+1]=B[j+1]（比如A[8]="d"時）。因此，准確的說法是，當j=0了時，我們增加i值但忽略j直到出現A[i]=B[1]為止。

最後的j:=P[j]是為了讓程序繼續做下去，因為我們有可能找到多處匹配。
這個程序或許比想像中的要簡單，因為對於i值的不斷增加，代碼用的是for循環。因此，這個代碼可以這樣形象地理解：掃描字元串A，並更新可以匹配到B的什麼位置。

現在，我們還遺留了兩個重要的問題：一，為什麼這個程序是線性的；二，如何快速預處理P數組。
為什麼這個程序是O(n)的？其實，主要的爭議在於，while循環使得執行次數出現了不確定因素。我們將用到時間復雜度的攤還分析中的主要策略，簡單地說就是通過觀察某一個變數或函數值的變化來對零散的、雜亂的、不規則的執行次數進行累計。KMP的時間復雜度分析可謂攤還分析的典型。我們從上述程序的j 值入手。每一次執行while循環都會使j減小（但不能減成負的），而另外的改變j值的地方只有第五行。每次執行了這一行，j都只能加1；因此，整個過程中j最多加了n個1。於是，j最多隻有n次減小的機會（j值減小的次數當然不能超過n，因為j永遠是非負整數）。這告訴我們，while循環總共最多執行了n次。按照攤還分析的說法，平攤到每次for循環中後，一次for循環的復雜度為O(1)。整個過程顯然是O(n)的。這樣的分析對於後面P數組預處理的過程同樣有效，同樣可以得到預處理過程的復雜度為O(m)。
預處理不需要按照P的定義寫成O(m^2)甚至O(m^3)的。我們可以通過P[1],P[2],...,P[j-1]的值來獲得P[j]的值。對於剛才的B="ababacb"，假如我們已經求出了P[1],P[2],P[3]和P[4]，看看我們應該怎麼求出P[5]和P[6]。P[4]=2，那麼P [5]顯然等於P[4]+1，因為由P[4]可以知道，B[1,2]已經和B[3,4]相等了，現在又有B[3]=B[5]，所以P[5]可以由P[4] 後面加一個字元得到。P[6]也等於P[5]+1嗎？顯然不是，因為B[ P[5]+1 ]<>B[6]。那麼，我們要考慮「退一步」了。我們考慮P[6]是否有可能由P[5]的情況所包含的子串得到，即是否P[6]=P[ P[5] ]+1。這里想不通的話可以仔細看一下：

1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ?

P[5]=3是因為B[1..3]和B[3..5]都是"aba"；而P[3]=1則告訴我們，B[1]和B[5]都是"a"。既然P[6]不能由P [5]得到，或許可以由P[3]得到（如果B[2]恰好和B[6]相等的話，P[6]就等於P[3]+1了）。顯然，P[6]也不能通過P[3]得到，因為B[2]<>B[6]。事實上，這樣一直推到P[1]也不行，最後，我們得到，P[6]=0。

最後補充一點：由於KMP演算法只預處理B串，因此這種演算法很適合這樣的問題：給定一個B串和一群不同的A串，問B是哪些A串的子串。

串匹配是一個很有研究價值的問題。事實上，我們還有後綴樹，自動機等很多方法，這些演算法都巧妙地運用了預處理，從而可以在線性的時間里解決字元串的匹配。

4. 數據結構 字元串 模式匹配問題 KMP演算法

你的程序本身思路沒有錯，但錯在以下幾點：
1.在程序中有字元串S和T，你用S[0]代表字元串的長度，但S是字元串，S[0]是長度嗎？
2.在main函數中，你輸入的S和T都是用gets(S)或gets(T),那麼它們都是以下標0開頭的，你應該要進行處理，使它以下標1作為開頭（可以這樣gets(&S[1]); 然後S[0] = strlen(&S[1]) + '0';在用S[0]作為長度的時候，把它從字元變成數字就行了)。

5. 串的應用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");
}
}

6. 演算法基礎 - 樸素模式匹配演算法、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]的值

7. 判斷兩個字元串是否匹配，其中字元串中包括通配符*或(串)。*代表0個或多個字元代表一個字元

給你一個用遞歸演算法寫的字元串匹配函數，
非常精練，你可以參考一下，希望能看懂。
輸入：
s，指向含通配符的匹配字元串，
d，指向要匹配的字元目標
返回值：
1，匹配一致
0，不能匹配

int StrMatch(const char *s,const char *d)
{ for(;*s;s++,d++)
{ if(*s=='*')
{ for(s++;;d++)
{ if(StrMatch(s,d))return 1;
if(*d==0)return 0;
}
}
if(*d==0)return 0;
if(*s!='?'&&*s!=*d)return 0;
}
return !(*d);
}

8. 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");
}
}

9. kmp 演算法原理

樸素演算法
先看看最「樸素」的演算法： ///find a template in a string. #include<string.h> #include<stdio.h> int Index(char *S, char *T, int pos) { int k=pos, j=0; while(k <strlen(S) && j<strlen(T))//未超出字元串的長度 { if (S[k] == T[j]) { ++k; ++j;} //如果相同，則繼續向後比較 else {k = k-j+1; j =0;} //如果不同，就回溯，重新查找 } if (j == strlen(T)) return k-strlen（T）; else return 0; }
編輯本段KMP演算法
一種由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人設計的線性時間字元串匹配演算法。這個演算法不用計算變遷函數δ，匹配時間為Θ(n)，只用到輔助函數π[1，m]，它是在Θ(m)時間內，根據模式預先計算出來的。數組π使得我們可以按需要，「現場」有效的計算(在平攤意義上來說)變遷函數δ。粗略地說，對任意狀態q=0，1，…，m和任意字元a∈Σ，π[q]的值包含了與a無關但在計算δ(q，a)時需要的信息。由於數組π只有m個元素，而δ有Θ(m∣Σ∣)個值，所以通過預先計算π而不是δ，使得時間減少了一個Σ因子。[1] KMP演算法是通過分析子串，預先計算每個位置發生不匹配的時候，所需GOTO的下一個比較位置，整理出來一個next數組，然後在上面的演算法中使用。
編輯本段KMP演算法的講解
當我們分析一個子串時，例如：abcabcddes. 需要分析一下，每個字元x前面最多有多少個連續的字元和字元串從初始位置開始的字元匹配。然後+1就行了（別忘了，我們的字元串都是從索引1開始的）當然，不要相同位置自己匹配，默認第一個字元的匹配數是0。
編輯本段定義
設字元串為 x1x2x3...xn ,其中x1，x2，x3，... xi，... xn均是字元，設ai為字元xi對應的整數。則a=m，當且僅當滿足如下條件：字元串x1x2...xm equals 字元串x(i-m+1)...xi-1 xi 並且x1x2...xm x(m+1) unequals x(i-m) x(i-m+1)...xi-1 xi。
編輯本段舉例
abcabcddes 0111234111 |----------------------默認是0 --| | |-----------------不能自己在相同位置進行字元匹配，所以這里認為沒有匹配字元串，所以0+1 =1，繼續從1開始匹配 ------| | |-----------前面的字元和開始位置的字元相同，所以是2,3,4 -----------| | | |-------不匹配只能取1。 希望能明白的是，如果開始字元是 Ch1的話，那麼我們就是要在串中第2個Ch1後面的位置開始自己和自己匹配，計算最大的吻合度。 程序寫出來就是： void GetNext(char* T, int *next) { int k=1,j=0; next[1]=0; while( k〈 T[0] ){ if (j ==0 || T[k] == T[j]) { ++k; ++j; next[k] = j; } else j= next[j]; } } 但是這個不是最優的，因為他沒有考慮aaaaaaaaaaaaaaaaaaab的情況，這樣前面會出現大量的1，這樣的演算法復雜度已經和最初的樸素演算法沒有區別了。所以稍微改動一下： void GetNextEx(char *T, char *next) { int k=1,j=0; next[1] = 0; while(k < T[0]) { if (j == 0 || T[k] == T[j]) { ++k; ++j; if (T[k] == T[j]) next[k] = next[j]; else next[k] = j; } else j = next[j]; } } 現在我們已經可以得到這個next字元串的值了，接下來就是KMP演算法的本體了： 相當簡單： int KMP(char* S, char* T, int pos) { int k=pos, j=1; while (k){ if (S[k] == T[j]){ ++k; ++j; } else j = next[j]; } if (j>T[0]) return k-T[0]; else return 0; } 和樸素演算法相比，只是修改一句話而已，但是演算法復雜度從O(m*n) 變成了：O(m)
編輯本段KMP演算法的偽代碼
KMP-MATCHER(T，P) 1n ← length[T] 2m ←length[P] 3π ← COMPUTE-PREFIX-FUNCTION(P) 4q ← 0△Number of characters matched. 5for i ← 1 to n△Scan the text from left to right. 6do while q>0 and P[q+1]≠T[i] 7do q ← π[q]△Next character does not match. 8if P[q+1]=T[i] 9then q ← q+1△Next character matches. 10if q=m△Is all of P matched? 11then print 「Pattern occurs with shift」 i-m 12q ← π[q]△Look for the next match. COMPUTE-PERFIX-FUNCTION(P) 1m ← length[P] 2π[1] ← 0 3k ← 0 4for q ← 2 to m 5do while k>0 and P[k+1]≠P[q] 6do k ← π[k] 7if P[k+1]=P[q] 8then k ← k+1 9π[q] ← k 10return π[1]
編輯本段KMP演算法的c++實現
//c++實現的KMP演算法，所有涉及字元串，其初始下標從0開始(上述演算法均是從1開始) //example: char s[100],t[100];cin>>s>>t;KMP(s,t); //獲取待查詢模式的next數組 int* get_next(char* T, int* next){ int i = 0, j = -1; int length = strlen(T); int *temp = next; *next = -1; while(i< length){ if(j==-1 || *(T+i)==*(T+j)){ i++; j++; //優化後的get_next方法，可以防止出現形如"aaaaab"這種模式的計算退化 if(*(T+i)!=*(T+j)) *(next+i)=j; else *(next+i)=*(next+j); } else j=*(next+j); } return temp; } //KMP演算法 int KMP(char *S, char *T){ int S_Length = strlen(S); int T_Length = strlen(T); //若模式長度大於字元串，則直接返回查詢失敗 if( S_Length < T_Length) return 0; int i = 0, j = 0; int* next = new int[T_Length]; get_next(T, next); while(i < S_Length && j < T_Length){ if(j == -1 || *(S+i) == *(T+j)){ i++; j++; } else j=*(next+j); } if(j>=T_Length) return i-T_Length; return 0; } 在此提供一個更簡明的適用於字元串的kmp實現： #include<iostream> #include<string.h> int next[100]; void getnext(char b[]) { int i=1,j=0; //i是每個位子，j是回退的位子 next[1]=0; while(i<=strlen(b)) { if(j==0||b[i-1]==b[j-1]) { i++; j++; next[i]=j; } else j=next[j]; //用上一個的 回退關系 } } int kmp(char a[],char b[]) { int i=1,j=1; //i是主串中的位子 ，j匹配串的位子 while(i<=strlen(a)&&j<=strlen(b)) { if(j==0||a[i-1]==b[j-1]) { i++; j++; } else j=next[j]; } if(j>strlen(b)) return i-strlen(b); else return 0; } int main() { char a[40],b[40]; printf("要匹配的主串：\n"); scanf("%s",a); printf("要匹配的子串：\n"); scanf("%s",b); getnext(b); printf("輸出next值：\n"); for(int i=1;i<=strlen(b);i++) printf("%d ",next[i]); printf("\n"); printf("%d",kmp(a,b)); system("pause"); main(); return 0; }
編輯本段串的最大匹配演算法
摘要：
給定兩個串S和T，長分別m和n，本文給出了一個找出二串間最大匹配的演算法。該演算法可用於比較兩個串S和T的相似程度，它與串的模式匹配有別。
關鍵詞：
模式匹配 串的最大匹配 演算法 Algorithm on Maximal Matching of Strings Lin YuCai Xiang YongHong Zhang ChunXia Zhang JianJun （Computer Science Department of Yunnan Normal University Kunming 650092） ABSTRACT Given Two Strings S of length m and T of length n，the paper presents an algorithm which finds the maximal matching of them. The algorithm can be used to compare the similarility of the two strings S and T, it is different with the strings' pattren matching. KEY WORDS Pattern Matching Maximal Matching of Strings Algorithm
編輯本段問題的提出
字元串的模式匹配主要用於文本處理，例如文本編輯。文本數據的存儲（文本壓縮）和數據檢索系統。所謂字元串的模式匹配[2]，就是給定兩個字元串S和T，長度分別為m和n，找出T中出現的一個或多個或所有的S，在這方面已經取得了不少進展[3][4][5][6][7][8][9][10][11]。本文從文本處理的另一個角度出發，找出兩個串的最大匹配，比較其相似程度[1]。它主要應用於文本比較，特別是在計算機輔助教學中。顯然前者要找S的完全匹配，而後者並無此要求。例如，若S=ABCD，T=EFABCDX，那麼模式匹配的結果就是找出了T中的一個ABCD，而我們演算法的結果就是S能與T的ABCD完全匹配，但是T中還有3個字元是比S多出來的，也就是說在S中有100%的字元與T中的匹配，而在T中有57%的字元與S中的匹配。若S= ABCDFE，T=AFXBECDY。則在模式匹配中S與T無匹配項，但在我們的演算法中就能發現T中存在A，B，C，D，但D後不存在E，F。而且S中也存在A，B，C，D，且具有順序性。這樣就能公正地評價S，T的區別。得知其相似程度。 文章的組織如下：首先介紹基本定義和問題的描述；第三節是演算法設計；最後是本文總結。
編輯本段問題的描述
設∑為任意有限集，其元稱為字元，w：∑→N為∑到N的函數，稱為∑的權函數（註：本文僅討論權值恆為1的情況）。∑*為∑上的有限字元串集合，那麼對任意S，T∈∑*，設S=a1a2…am，T=b1b2…bn，m>0，n>0。記<m>={1,2, …,m},<n>={1,2, …,n}，則稱{(i,j)∣i∈<m>，j∈<n>，ai=bj}為S與T的匹配關系集，記作M（S，T），稱M為S與T的一個（容許）匹配，若對任意（i,j）, ( i',j' )∈，① i< i'，當且僅當j< j'，② i= i'當且僅當j= j'。S與T的匹配中滿足 最大者，稱為S與T的最大匹配。若C(i,j)為N上的m×n矩陣，且滿足： 則稱矩陣C為串S與T的匹配關系陣。 於是求串S與T的最大匹配，等價於求C中的一個最大獨立點集M，它滿足，若ci,j，ci',j'∈M，則i< i' 當且僅當j< j'，i=i'當且僅當j=j'。我們稱這樣的最大獨立點集為C的最大C-獨立點集。 例：設∑為所有字母的集合，對任意x∈∑，w（x）≡1，設S與T分別為：S=「BOOKNEWS」，T=「NEWBOOKS」。則我們可以得到S與T兩個匹配： 這里=5； 這里 =4。 顯然為串S與T的最大匹配。 S與T的匹配關系陣C可表示如下： 其中帶圈的部分為一最大C-獨立點集。
編輯本段演算法設計
我們僅就權值為一的情況進行討論。 設S和T為任意給定串，C為的S與T匹配關系陣，那麼由2的討論知，求S與T的最大匹配問題，等價於求C的最大C-獨立點集問題。因而，為了解決我們的問題，只要給出求C的最大C-獨立點集的演算法就可以了。 顯然，為了求出C的最大C-獨立點集，我們可以採用這樣的方法：搜索C的所有C-獨立點集，並找出它的最大者。這種方法是可行的，但並不是非常有效的。這會使問題變得很繁，復雜度很大。因此，我們先對問題進行分析。 在下面的討論中，我們把C的任一C-獨立點集={ai1,j1，…，ais,js}，記作=ai1,j1…ais,js，i1 <…< is。於是可看作陣C中以1為節點的一條路，滿足：對路中的任意兩節點，均有某一節點位於另一節點的右下方。稱這種路為右下行路。 於是求C-獨立點集等價於求陣C的右下行路。這種求右下行路的搜索可以逐行往下進行。 命題1. 若 =αai,jβ和ψ=α'ai,jσ為C的兩個C-獨立點集，且α為α'的加細，則存在C-獨立點集'=αai,jδ，滿足≥。 命題2. 若 =αai,jβ和ψ=α'ai+k,jσ為C的兩個C-獨立點集，且≥，則存在C-獨立點集'=αai,jδ，滿足≥。 命題3. 若 =αai,jβ和ψ=α'ai,j+kσ為C的兩個C-獨立點集，且≥，則存在C-獨立點集'=αai,jδ，滿足≥。 由命題1知，在搜索右下行路的過程中，如果已獲得了某一C-獨立點集的某一初始截段αai,j和另一C-獨立點集ψ的某一初始截段α'ai,j，且有≤，則我們可以停止對ψ的進一步搜索。 由命題2知，在搜索右下行路的過程中，在某一列j存在某兩個C-獨立點集的某初始截段=ai1,j1…ais,j和ψ=al1,m1…alt,j，如果≥，但lt>is，則我們可以停止對ψ的進一步搜索。 由命題3知，在搜索右下行路的過程中，在某一行i存在某兩個C-獨立點集的某初始截段=ai1,j1…ai,js和ψ=ai1,m1…ai,mt，如果≥，但mt>js，則我們可以停止對ψ的進一步搜索。 由此可見，並不要求搜索所有C的最大C-獨立點集，而可以採用比這簡單得多的方法進行計算。那麼按照我們上面的三個命題，來看如下實例： 首先我們得到=B（在上的節點用①表示），我們向右下方找路，可以發現，在第4列有兩個1，根據命題2，我們選擇上面的一個1，也就是說選擇第1行的那個1，而不要第2行的那個1。同時我們也發現在第1行也有兩個1，由命題3知，我們選擇左邊的那個1，即第4列的那個1。此時=BO。但是當我們的演算法運行到第4行時，=BOOK，由於K在第3行第6列，而本行的1在第1列，在路最後一個節點K的左邊，那麼我們必須新建一條路ψ，因為我們並不能確定是否以後就有≥，當演算法運行到第6行時，=BOOK，ψ=NEW，=4，=3，我們將S鏈到路上，此時我們得到最長右下行路=BOOKS，=5。這樣我們就可以計算出這兩個字元串的匹配程度。 在我們的演算法設計過程中，用到了兩個技巧。技巧之一，矩陣C不用存儲，是動態建立的，節省了空間。技巧之二，本演算法並不要求所有的S與T中所有的元素都相互進行比較，也並不存儲所有的右下行路，節省了時間和空間。由矩陣中1的出現情況可見，本演算法所需的空間和時間都遠小於O（mn）
編輯本段結束語
本文給出了一個與模式匹配不同的，具有若干應用的，串的最大匹配演算法，該演算法已經在機器上實現，達到了預期的效果。本文僅討論權值恆為1的情況，對於權值任意的情形不難由此得到推廣。
編輯本段C語言代碼(C Code)
#include<stdio.h> #include<string.h> void getnext(int next[],char s[],int l) { int i=1,j=0; next[1]=0; while(i<l) { if(j==0 || s[i]==s[j]) { i++;j++; next[i]=j; } else j=next[j]; } } int KMP(char s1[],char s2[],int l1,int l2,int next[]) { int i,j; i=j=1; while(i<=l1 && j<=l2) { if(j==0||s1[i]==s2[j]) { i++;j++; } else j=next[j]; } if(j>l2) return(i-l2); return 0; } int main() { int next[10001],ans; char s1[10001],s2[10001],l1,l2; scanf("%s",s1+1); scanf("%s",s2+1); l1=strlen(s1+1); l2=strlen(s2+1); getnext(next,s2,l2); ans=KMP(s1,s2,l1,l2,next); if(ans!=0) printf("%d\n",ans); else printf("No!\n"); system("pause"); return 0; }
編輯本段KMP演算法的pascal實現
var next:array [1 ..1000001] of longint; s,t:ansistring; procere get_next(t:ansistring); var j,k:integer; begin j:=1; k:=0; while j<length(t) do begin if (k=0) or (t[j]=t[k]) then begin inc(j); inc(k); next[j]:=k; end else k:=next[k]; end; end; function index(s:ansistring;t:ansistring):longint; var i,j:longint; begin get_next(t); index:=0; i:=1; j:=1; while (i<=length(s))and(j<=length(t)) do begin if (j=0)or(s[i]=t[j]) then begin inc(i); inc(j); end else j:=next[j]; if j>length(t) then index:=i-length(t); end; end; begin readln(s); readln(t); writeln(index(s,t)) end.
編輯本段KMP播放器
K-multimedia player的縮寫
來自韓國的影音全能播放器，與Mplayer一樣從linux平台移植而來的Kmplayer(簡稱KMP)幾乎可以播放您系統上所有的影音文件。通過各種插件擴展KMP可以支持層出不窮的新格式。強大的插件功能,直接從Winamp繼承的插件功能，能夠直接使用winamp的音頻 ，輸入，視覺效果插件，而通過獨有的擴展能力，只要你喜歡，可以選擇使用不同解碼器對各種格式進行解碼。 KMPlayer The Professional Media Player! 它支持 Winamp 2/5 的輸入、常規、DSP、視覺效果、媒體庫插件。無須注冊表支持直接調用 Directshow 濾鏡！FFdshow 的視覺特效系統~超強的 GUI 界面~安裝電視卡後可以直接代替原軟體直接收看電視~支持播放 DVD/VCD 以及絕大多數電腦的媒體文件（AVI 支持 Xvid/DivX/3vid/H264 OGG/OGM/MKV 容器/AC3/DTS 解碼~Monkey Audio 解碼~）強烈推薦！此播放器除了會將自己的配置信息寫入注冊表外絕對綠色~ KMplayer內置目前常見的所有解碼器，包括real,QT等。 另外KMplayer安裝版也是目前很少見的檢查流氓軟體的安裝方式，如果一旦有惡意的漢化小組漢化並捆綁了流氓軟體。該安裝程序自動會識別，並作出提示，建議用戶不要安裝，雖然不是特別准確，但KMplayer的無廣告及第三方插件的特點使其深受好評。 目前韓國官方已經在Kmplayer里自帶了中文字型檔，只要用戶是中文系統，軟體就會自動識別，十分方便。 KMP版本: KMPlayer3.0.0.1439

10. kmp演算法的介紹

KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是利用匹配失敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是實現一個next()函數，函數本身包含了模式串的局部匹配信息。