1. 數據結構關於串的KMP演算法的理解高手請進
KMP 演算法是一種字元串的模式匹配演算法，參看嚴蔚敏數據結構一書，裡面講的很清楚。
基本的字元串匹配演算法是將被匹配的字元串S和模式串T 逐個字元進行比較。例如:S中有10個字元，T中有5個字元。S串初始的匹配位置為3.則從S中的第3個字元與T中的第一個字元匹配，若相同則S的第4個字元與T中的第2個字元匹配。直到匹配成功或者出現失配字元。當出現失配情況下，移動標識S中當前進行比較的字元指針，會退到第4個字元處。然後，重復這一過程。簡單說，基本的字元匹配演算法是通過移動被匹配的字元串S，進行比較字元的指針位置來完成字元匹配的。
而KMP演算法剛好相反，在整個匹配過程中S中當前比較字元的指針並不發生回退現象，當出現S中的字元與T中的字元失配的時候。通過改變T的當前比較字元位置的指針來確定當前S中的字元該與T中哪個字元進行比較。簡單說，通過模式字元串T的當前比較字元的指針的回退來完成字元匹配。
當理解了KMP演算法通過改變T的當前比較字元位置的指針來完成匹配時，接下來要理清的是模式字元串T中的字元指針在失配的情況下是如何移動的。
以嚴蔚敏數據結構一書中KMP為例，對於模式字元串T，KMP維護了一個對應於T中每個字元弱發生失配情況下，指針回退到哪一位置的數組。當被匹配串S與模式串T發生失配的情況下，T讀取數組中相應記錄的位置，講指針回退。如果回退後仍然失配則S的當前比較字元位置指針+1，T串指針回到第一個字元處。
由此可見獲取數組中存儲的數據是KMP演算法的關鍵，書中的公式看起來有點抽象。數組中的存儲指針的位置是根據，模式串T與自身的匹配過程獲取的。
實際上是說，模式串T的第一個字元，如果出現失配則不會回退；當前比較位置的字元向前N-1位的子串恰好與T中從第一個字元起止N-1個字元形成的子串相等，且N小於當前位置，滿足這些條件的N的最大值即為T當前位置指針回退的位置，然後迭代此過程，直到T本身匹配或回退到第一個字元位置仍不匹配，則當前位置的對應的回退位置指針指向T中的第一個字元所在位置。
講的還不是很清楚，主要是對比一下基本的字元匹配演算法和KMP的不同。一個是通過移動被匹配字元串比較字元的指針來實現匹配，一個是移動模式字元串的當前比較字元的位置指針來實現匹配。對於匹配串字元回退位置這個計算書中已經很清楚，根據演算法單步調試一次自然就理解了。
2. 什麼是KMP演算法
KMP就是串匹配演算法
運用自動機原理
比如說
我們在S中找P
設P＝{ababbaaba}
我們將P對自己匹配
下面是求的過程:{依次記下匹配失敗的那一位}
[2]ababbaaba
......ababbaaba[1]
[3]ababbaaba
........ababbaaba[1]
[4]ababbaaba
........ababbaaba[2]
[5]ababbaaba
........ababbaaba[3]
[6]ababbaaba
..............ababbaaba[1]
[7]ababbaaba
..............ababbaaba[2]
[8]ababbaaba
.................ababbaaba[2]
[9]ababbaaba
.................ababbaaba[3]
得到Next數組『0,1,1,2,3,1,2,2,3』
主過程：
[1]i:=1 j:=1
[2]若(j>m)或(i>n)轉[4]否則轉[3]
[3]若j=0或a[i]=b[j]則【inc(i)inc(j)轉[2]】否則【j:=next[j]轉2】
[4]若j>m則return(i-m)否則return -1;
若返回－1表示失敗，否則表示在i-m處成功
若還不懂mail:[email protected]
參考一下這里吧:
http://www.chinaaspx.com/archive/delphi/4733.htm
3. 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);
}
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. 急！！急！！急！！數據結構（C語言版）程序設計題： 使用KMP演算法實現一個模式匹配。
#include <cstring>
#include <iostream>
using namespace std;
//修正後的求next數組各值的函數代碼
void get_nextval(char const* ptrn, int plen, int* nextval)
{
int i = 0; //i是從0開始的
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //循環的if部分
{
++i;
++j;
if( ptrn[i] != ptrn[j] ) //++i，++j之後，再次判斷ptrn[i]與ptrn[j]的關系
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else //循環的else部分
j = nextval[j];
}
}
void print_progress(char const* src, int src_index, char const* pstr, int pstr_index)
{
cout<<src_index<<"\t"<<src<<endl;
cout<<pstr_index<<"\t";
for( int i = 0; i < src_index-pstr_index; ++i )
cout<<" ";
cout<<pstr<<endl;
cout<<endl;
}
//int kmp_seach(char const*, int, char const*, int, int const*, int pos) KMP模式匹配函數
//輸入：src, slen主串
//輸入：patn, plen模式串
//輸入：nextval KMP演算法中的next函數值數組
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
{
int i = pos;
int j = 0;
while ( i < slen && j < plen )
{
if( j == -1 || src[i] == patn[j] )
{
++i;
++j;
}
else
{
j = nextval[j];
//當匹配失敗的時候直接用p[j_next]與s[i]比較，
//下面闡述怎麼求這個值，即匹配失效後下一次匹配的位置
}
}
if( j >= plen )
return i-plen;
else
return -1;
}
int main()
{
std::string src = "";
std::string prn = "abac";
int* nextval = new int[prn.size()];
//int* next = new int[prn.size()];
get_nextval(prn.data(), prn.size(), nextval);
//get_next(prn.data(), prn.size(), next);
for( int i = 0; i < prn.size(); ++i )
cout<<nextval[i]<<"\t";
cout<<endl;
cout<<"result sub str: "<<src.substr( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )<<endl;
system("pause");
delete[] nextval;
return 0;
}
望樓主採納！
6. 數據結構KMP演算法
#include <string.h>
/*在此定義一個int型數組next[],next[j]對應於當子串在位置j比較失敗時的下一次匹配時子串的開始位置，由子串決定。*/
int StrIndex(char *S,char *T)
{int i,j;
i=0;
j=0;
int Slen=strlen(S);
int Tlen=strlen(T);
while((j<=(Tlen-1))&&((Slen-1-i+1)>=(Tlen-1-j+1)))
{if(S[i]==T[j]) {i++;
j++;}
else {
j=next[j];
if(j==-1){i++;j++;}
}
}
if(j>(Tlen-1)) return (i-j+1);
else return 0;
}
如：
S="a b a b c a b a a b c a a b a a b a b c a a b"
T="a b a a b a b c"
定義
int next[8]={-1,0,0,1,0,0,3,2};
7. 數據結構 字元串 模式匹配問題 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]作為長度的時候，把它從字元變成數字就行了)。
8. 數據結構與演算法——字元串匹配問題(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種情況
9. 數據結構里實現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];
}
}
10. 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，繼續進行比較。