kmp演算法
① KMP演算法
演算法3.5——KMP演算法
1. 在串S和串T中分別設比較的起始下標i和j；
2. 循環直到S中所剩字元長度小於T的長度或T中所有字元均比較完畢
2.1 如果S[i]=T[j]，則繼續比較S和T的下一個字元；否則
2.2 將j向右滑動到next[j]位置，即j=next[j]；
2.3 如果j=0，則將i和j分別加1，准備下一趟比較；
3. 如果T中所有字元均比較完畢，則返回匹配的起始下標；否則返回0；
void GetNext(char T[ ], int next[ ])
{
next[1]=0;
j=1; k=0;
while (j<T[0])
if ((k= =0)| |(T[j]= =T[k])) {
j++;
k++;
next[j]=k;
}
else k=next[k];
}
② 求kmp演算法的詳細解釋。（最好附上能運行的程序）
t;i),那麼next[i]就是所有這樣的j的最大值
形象地說,就是假如第i+1個字元匹配失敗之後,下一個可能匹配位置至少應該往後挪動多少
就"abaabc"而言
next[1]=0
next[2]=0
next[3]=1
next[4]=1
next[5]=2
next[6]=0
計算過程基本上抄自演算法導論,假設str長度為n
k=0;//k表示當前匹配了多少位
next[1]=0;
for (i=1;i<n;i++)
{
while (k && str[i]!=str[k]) k=next[k];
if (str[i]==str[k]) k++;
next[i+1]=k;
}
之後計算str和某個長度為m的字元串text匹配的過程基本上是一樣的
k=0;//用於記錄str最長能夠有前k位是text的前i+1個字元的後綴
for (i=0;i<m;i++)
{
while (k && text[i]!=str[k]) k=next[k];//發現不能匹配的時候就把str往後挪
if (text[i]==str[k]) k++;
if (k==n) printf("在位置%d處找到一個匹配\n",i+1-n);
}
對照著後面這一段很容易理解第一段
③ KMP演算法問題
一般的KMP演算法
討論一般情況。
假設
主串：s: 『s⑴ s⑵ s⑶ ……s(n）』 ;
模式串 ：p: 『p⑴ p⑵ p⑶…..p(m）』
把課本上的這一段看完後，繼續
現在我們假設 主串第i個字元與模式串的第j(j<=m）個字元『失配』後，主串第i個字元與模式串的第k(k<j）個字元繼續比較
此時，s(i）≠p(j），有
主串：s⑴…… s(i-j+1）…… s(i-1） s(i) ………….
|| （相配） || ≠（失配）
匹配串：p⑴ ...........p(j-1） p(j)
由此，我們得到關系式：
『p⑴ p⑵ p⑶…..p(j-1）』 = 』 s(i-j+1）……s(i-1）』
由於s(i）≠p(j），接下來s(i）將與p(k）繼續比較，則模式串中的前（k-1）個字元的子串必須滿足下列關系式，並且不可能存在 k』>k 滿足下列關系式：（k<j),
『p⑴ p⑵ p⑶…..p(k-1）』 = 』 s(i-k+1）s(i-k+2）……s(i-1）』
即：
主串：s⑴……s(i-k +1） s(i-k +2） ……s(i-1） s(i) ………….
|| （相配） || ||（有待比較）
匹配串：p⑴ p⑵ ……..... p(k-1） p(k)
我們把前面總結的關系綜合一下
有：
s⑴…s(i-j +1）… s(i-k +1） s(i-k +2） …… s(i-1） s(i) ……
|| （相配） || || || ≠（失配）
p⑴ ……p(j-k+1） p(j-k+2） …...... p(j-1） p(j)
|| （相配） || ||（有待比較）
p⑴ p⑵ ……...... p(k-1） p(k)
由上，我們得到關系：
'p⑴ p⑵ p⑶…..p(k-1）』 = ' p(j-k+1）p(j-k+2）……p(j-1）』
接下來看「反之，若模式串中存在滿足式（4-4）。」這一段。看完這一段，如果下面的看不懂就不要看了。直接去看那個next函數的源程序。（偽代碼）
K 是和next有關系的，不過在最初看的時候，你不要太追究k到底是多少，至於next值是怎麼求出來的，我教你怎麼學會。
課本83頁不是有個例子嗎？就是 圖4.6
你照著源程序，看著那個例子慢慢的推出它來。看看你做的是不是和課本上正確的next值一樣。
在理解上面代碼的基礎上，建議自己尋找一些KMP演算法的練習，也可以自己寫兩個較為簡單的字元串進行人腦模擬這種方法的練習，以加深對演算法的理解。
④ KMP演算法詳細代碼
private int KMP(String inText, String inMode)
{
if (inText.Length < inMode.Length)
{
return -1;
}
int[] arrNext = new int[inMode.Length + 1];
this.Next(inMode, arrNext);
int i, j; // i是主串游標 j是模式串游標
for (i = j = 0; i < inText.Length && j < inMode.Length; )
{
if (j == -1 || // 模式串游標已經回退到第一個位置
inText[i] == inMode[j]) // 當前字元匹配成功
{ // 滿足以上兩種情況時兩個游標都要向前進一步
++i;
++j;
}
else // 匹配不成功,模式串游標回退到當前字元的arrNext值
{
j = arrNext[j];
}
}
if (j >= inMode.Length)
{
return i - inMode.Length;
}
else
{
return -1;
}
}
private void Next(String inMode, int[] arrNext)
{
arrNext[0] = -1;
for (int i = 0, j = -1; i < inMode.Length; )
{ // i是主串游標 j是模式串的游標
if (j == -1 || // 如果模式串游標已經回退到第一個字元
inMode[i] == inMode[j]) // 如果匹配成功
{ // 兩個游標都向前走一步
++i;
++j;
arrNext[i] = j; // 存放當前的arrNext值為此時模式串的游標值
}
else // 匹配不成功j就回退到上一個arrNext值
{
j = arrNext[j];
}
}
}
⑤ KMP演算法中的nextval函數值的原理，求詳細推導
1 get_nextval(int *nextval,const char *string)
2 {
3 int num=strlen(string);
4 int i=0,j=-1;
5 nextval[0]=-1;
6 while(i<num)
7 {
8 if(j==-1||string[i]=string[j])
9 {
10 i++;
11 j++;
12 if(string[i]==string[j])
13 {
14 nextval[i]=nextval[j];
15 }
16 else
17 {
18 nextval[i]=j;
19 }
20 }
21 else
22 {
23 j=next[j];
24 }
25 }
kmp的思想主要是通過nextval數組來指示「假如在子串與主串匹配過程中在某一位(假設為 j )匹配失敗（不相等）時，子串應回到的位置。」以此區別於樸素模式匹配的一旦在某位匹配失敗，就從頭比較的特點。所以在生成與子串等長的nextval數組時，nextval數組每一個元素標識的就應該是當在子串的第j位與主串匹配失敗時，應回到子串的哪一位。
設子串string為"abqabc"。主串為"abqabqabc"；生成nextval的思想是：假設目前 j 和 i 各處string的某一個位置，對比string[j]和string[i]（代碼第8行），若相等，j 和 i 都向前一步，j , i 向前一步（代碼10~11行）是為了下一次匹配，同時是為了在nextval[i]記錄當子串與主串匹配失敗時應回到子串的哪一位繼續比較下去（代碼第14或18行）。比如說當子串與主串在第六位（子串的c跟主串的q）匹配失敗時，我們會希望nextval[5]記錄的是2，這樣"ab"就不需重新匹配。
可以看到在子串的 c 之前，"abqab" 是前綴(ab)與後綴(ab)相等的，有兩位，所以在nextval[5]記錄 2 ，意思就是當 c 與主串匹配失敗時，直接回到子串string[2]繼續比較即可。
在製作nextval數組的過程中，i只會往前，j如果遇到前綴string[j]不等於後綴string[i]時會回溯，往回找，看能不能找到與後綴相等的前綴。比如子串為"abqabac"，製作nextval數組時比較到第三位(q)跟第六位(a)時，此時q不等於a，所以j往回找，拿第二位（b）跟第六位（a）比較，還是不相等，繼續往回找，找到一個位（a）跟第六位（a），相等，則在nextval[5]記錄nextval[0]的值，即-1，這時如果子串跟主串的匹配在子串的第六位（a）匹配失敗了，則直接略過主串的這一位，子串從頭開始與主串的下一位繼續進行匹配。
⑥ 各位面過BAT的同學,你們有沒有被考過KMP演算法
三家都面過，也許是我運氣好，沒有碰到過。其實KMP演算法效率不是很高，理解起來也不容易。如果面試官跟你聊字元串匹配演算法，你完全可以說點其他演算法裝逼。給你一個網頁，希望能幫助到你。4795369請採納最佳答案~
⑦ 誰知道KMP演算法的簡易理解
int f[50];//失敗函數
int i = 0, j = 1;
f[0] = -1;
for (j=1;j<n;j++)
{
i = f[j-1];
while (*(y+j) != *(y+i+1) && i>=0)
i = f[i];
if (*(y+j)==*(y+i+1))
f[j] = i+1;
else
f[j] = -1;
}
在本程序中失敗函數意思為 f[j] = 最大的 k 使得匹配模板前j+1個字元中 前k+1個字元和後k+1個字元相等
所以在j的位置上匹配失敗後可以跳到 f[j-1] + 1 的位置上進行匹配
不懂加QQ331012005
我們看到在簡單匹配演算法中，當主串和子串的字元比較不相等時，
主串的字元指針ps需返回本趟開始處的下一個字元，而子串的指針pp則回到子串的起始字元，
這種回溯顯然是費時的。如果仔細觀察，可以發現這樣的回溯常常不是必須的。
設主串s="s0 s1 … sn－1"，模式串p="p0 p1 … pm－1"，並設字元比較在si≠pj處失配。如果考察p串，發現
p0 p1… pk－1 = pj－k pj－k+1… pj－1
p0 p1 … pj－1的前綴子串，pj－k pj－k+1… pj－1 是p0p1 … pj－1的後綴子串。由於匹配在si≠pj處失敗，所以必有
pj－k… pj－2 pj－1= si－k… si－2 si－1
因此
p0… pk－2 pk－1 = si－k… si－2 si－1
那麼，下一趟比較可以從si和pk處開始。
所以可以定義失敗函數如下
－1(當j=0時)
f(j)= max{k|0＜k＜j且p0 p1 … pk－1= pj－k pj－k+1… pj－1}存在
0(其他情況)
設比較在si、pj處失敗，f(j)≥0表示下一趟比較從si與pf(j)處開始；
f(j)=－1表示p0 si, 下一趟比較應從p0與si＋1開始。
⑧ 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，繼續進行比較。
⑨ kmp演算法的介紹
KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是利用匹配失敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是實現一個next()函數，函數本身包含了模式串的局部匹配信息。
⑩ kmp演算法中的next到底是什麼意思啊
next[j]表代表j之前的字元串的真前綴和真後綴最大匹配長度，它的構成和kmp演算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值