php實現kmp演算法,kmp演算法詳解

本文目錄一覽：

• 1、KMP演算法，輸三組主串S和模式串P，輸出模式串的Next(j)函數值，及該P在S中的位置的定
• 2、KMP模式匹配演算法是什麼？
• 3、KMP演算法的原理及其應用
• 4、KMP演算法詳細代碼
• 5、kmp演算法詳解
• 6、數據結構里實現KMP演算法

KMP演算法，輸三組主串S和模式串P，輸出模式串的Next(j)函數值，及該P在S中的位置的定

KMP演算法查找串S中含串P的個數count

#include iostream

#include stdlib.h

#include vector

using namespace std;

inline void NEXT(const string T,vectorint next)

{

//按模式串生成vector,next(T.size())

next[0]=-1;

for(int i=1;iT.size();i++ ){

int j=next[i-1];

while(T[i]!=T[j+1] j=0 )

j=next[j] ; //遞推計算

if(T[i]==T[j+1])next[i]=j+1;

else next[i]=0; //

}

}

inline string::size_typeCOUNT_KMP(const string S,

const string T)

{

//利用模式串T的next函數求T在主串S中的個數count的KMP演算法

//其中T非空，

vectorint next(T.size());

NEXT(T,next);

string::size_type index,count=0;

for(index=0;indexS.size();++index){

int pos=0;

string::size_type iter=index;

while(posT.size() iterS.size()){

if(S[iter]==T[pos]){

++iter;++pos;

}

else{

if(pos==0)++iter;

else pos=next[pos-1]+1;

}

}//while end

if(pos==T.size()(iter-index)==T.size())++count;

} //for end

return count;

}

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

{

string S=”abaabcacabaabcacabaabcacabaabcacabaabcac”;

string T=”ab”;

string::size_type count=COUNT_KMP(S,T);

coutcountendl;

system(“PAUSE”);

return 0;

}

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改進演算法的模式匹配過程示意

KMP演算法的原理及其應用

KMP演算法是通過分析子串，預先計算每個位置發生不匹配的時候，所需GOTO的下一個比較位置，整理出來一個next數組，然後再上面的演算法中使用。

講解一下：

當我們分析一個子串時，例如：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

——| | |———–前面的字元和開始位置的字元相同，所以是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 i=k,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 (jT[0]) return k-T[0];

else return 0;

}

和樸素演算法相比，只是修改一句話而已，但是演算法複雜度從O(m*n) 變成了：O(m)

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;isize;i++){

//當找到第一個匹配的字元時，即j0時才會執行這個循環

//或者說p2中的j++會在p1之前執行（限於第一次執行的條件下）

//p1

while(j0 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;iparSize;i++){

//當找到第一個匹配的字元時，即j0時才會執行這個循環

//或者說p2中的j++會在p1之前執行（限於第一次執行的條件下）

//p1

while(j0 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模式匹配演算法

KMP演算法是一種改進的字元串匹配演算法,其關鍵是利用匹配失敗後的信息,盡量減少模式串與主串的匹配次數以達到快速匹配的目的明[4]。

求得模式的特徵向量之後，基於特徵分析的快速模式匹配演算法(KMP模式匹配演算法)與樸素匹配演算法類似，只是在每次匹配過程中發生某次失配時，不再單純地把模式後移一位，而是根據當前字元的特徵數來決定模式右移的位數[3]。

include “string. h”

#includeassert. 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] j0)

j=N[j-1];

if(P[j]==T[i])

j++;

if(j ==P.strlen())

return(1-j+1);//匹配成功,返回該T子串的開始位置

}

return (-1);

}

數據結構里實現KMP演算法

KMP演算法的C語言實現2007-12-10 23:33

基本思想：

這種演算法是D.E.Knuth 與V.R.Pratt和J.H.Morris同時發現的，因此人們稱為KMP演算法。此演算法可以在O(n+m)的時間數量級上完成串的模式匹配操作。

其基本思想是：每當匹配過程中出現字元串比較不等時，不需回溯i指針，而是利用已經得到的「部分匹配」結果將模式向右「滑動」儘可能遠的一段距離後，繼續進行比較。

#include stdio.h

#include string.h

int index_KMP(char *s,char *t,int pos);

void get_next(char *t,int *);

char s[10]=”abcacbcba”;

char t[4]=”bca”;

int next[4];

int pos=0;

int main()

{

int n;

get_next(t,next);

n=index_KMP(s,t,pos);

printf(“%d”,n);

return 0;

}

int index_KMP(char *s,char *t,int pos)

{

int i=pos,j=1;

while (i=(int)strlen(s)j=(int)strlen(t))

{

if (j==0||s[i]==t[j-1])

{

i++;

j++;

}

else j=next[j];

}

if (j(int)strlen(t))

return i-strlen(t)+1;

else

return 0;

}

void get_next(char *t,int *next)

{

int i=1,j=0;

next[0]=next[1]=0;

while (i(int)strlen(t))

{

if (j==0||t[i]==t[j])

{

i++;

j++;

next[i]=j;

}

else j=next[j];

}

}