kmp演算法next
『壹』 kmp演算法next(j)怎麼算出來的
int first=-1,last=0;
len=strlen(ch);
while(last<len){
if(ch[first]==ch[last] || first==-1){
first++;last++;
next[last]=first;
}
else
first=next[first];
}
用自己和自己KMP然後得出next[]
最後的出來的就是next[]了，當然我這個next[]是初值為-1的，你書上寫的應該是最大匹配值，就是將我的全部左移一位的結果
『貳』 模式匹配KMP演算法裡面next里保存的值有什麼用
next數組存儲的數據是用來當模式串與主串不匹配的時候要模式串回退到第幾個字元與主串再重新匹配，我們知道KMP演算法的主串是不回朔的，當不匹配的時候我們不是退回到開始位置重新匹配，而是利用已經匹配的結果將模式串回朔到下一個位置，這個位置比開始位置更近一步;
簡單的說就是next[ j ]的值保存的是當模式串中第 j 個字元與主串第 i 個字元不匹配時候，模式串中的哪個字元 重新與主串第 i 個再匹配，這樣總的字元比較次數比從開始位置比較的次數就少了。
『叄』 KMP演算法求next數組的問題
字元串如果是以0為下標的話next[7]是0，只有最後一位與第一位相等。
在第i個字元前面的i-1個字元裡面，
從開頭開始的1個字元與最後1個字元是否相等，若不是，則next[i]=0；
從開頭開始的2個字元與最後2個字元是否相等，若不是，則next[i]=1；
從開頭開始的3個字元與最後3個字元是否相等，若不是，則next[i]=2；
前綴next數組的求解演算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字元串長度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推。
(3)kmp演算法next擴展閱讀：
kmp演算法完成的任務是：給定兩個字元串O和f，長度分別為n和m，判斷f是否在O中出現，如果出現則返回出現的位置。常規方法是遍歷a的每一個位置，然後從該位置開始和b進行匹配，但是這種方法的復雜度是O(nm)。kmp演算法通過一個O(m)的預處理，使匹配的復雜度降為O(n+m)。
『肆』 KMP演算法中的next數組如何計算
一個串的next數組，可以這樣理解
對於next[i]的值，等於該串0~i-1的這個串中，前幾個字元組成的串，與後幾個字元完全相同。
舉個例吧，ababc，next數組下標就是0~4的范圍啦~~
首先next[0]=0，這是肯定的，其實next[0]沒意義。。。
計算next[1]，先看原串該位置之前的子串，即a，從前往後數1，與從後往前數1，串都是a，相等，故next[1]=1
然後next[2]，前綴串為ab，從前往後數1，與從後往前數1，子串分別為a,b，不等，所以next[2]=0
next[3]，對於前綴串aba，從前往後數1，與從後往前數1，串都是a相等。但是，數到2時，ab與ba不等，故next[3]=1
對於next[4]，前綴串abab，雖然去長度1時，子串不等。但數到2時，子串均為ab，相等。故next[4]=2
以此類推，就是數前綴串中，前數幾個與後數幾個，取到子串相等時，最大數到幾。當然，這樣數不能數到盡頭。。。
『伍』 誰能解釋數據結構中KMP演算法的next函數
假如str的前j個字元是前i個字元的後綴(j<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演算法求next值的問題
額這個問題之前沒多久給別人解答過，我就直接搬過來了……
————————————————————————————————————————
好吧~KMP當初我也想了挺久的~很巧妙的演算法啊！相必復制網路什麼的你也不會看的了所以我手打吧…下面是我的理解~
為了解說方便我把長的稱為文本串，短的稱為目標串~
常規的匹配演算法是把目標串一位一位地右移，跟文本串比較，而KMP則是跳著右移~
舉幾個例子相信你就懂了
————————————————————————————————————————
比如有一目標串為ababaca，當前位置匹配了前5個，也就是匹配了ababa，後面兩個不匹配
這說明了文本串當前位置也是ababa
顯然右移一位是不行的，因為從目標串可以看出(abab)a與a(baba)括弧里的內容不相等
而右移兩位是可能可行的~因為可以看出(aba)ba與ab(aba)括弧里的內容是相等的，這意味著移動兩位後，目標串前三位aba是肯定匹配的~因為移動前也匹配~
————————————————————————————————————————
再舉一個例子~比如有目標串abcab，當前位置匹配了前兩個ab
那麼就需要右移3個位置，因為(ab)cab與abc(ab)括弧里內容相同，移動後有可能會匹配~
————————————————————————————————————————
懂了么？表達能力有限…我也不能講得更好了…具體代碼網上一大堆，《演算法導論》裡面也有~我當初就是在算導里學會的！
如果懂了，希望有追加分啊，手打累死！！！
不懂的話，追問吧……
『柒』 kmp演算法中的next到底是什麼意思啊
next[j]表代表j之前的字元串的真前綴和真後綴最大匹配長度，它的構成和kmp演算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值
『捌』 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演算法的next存什麼
即使演算法是特定的，存什麼內容也是實現相關的。
對你這個數據設定，我猜測：
next[k] 表示的是，若目標字元與第 k 個字元不匹配時，則『下一步』嘗試將之和第幾個字元做比較。
index:-1012345
value:|abcabd
next:-100012
『拾』 給出字元串在KMP演算法中的Next數組
逐個查找對稱串。
只要循環遍歷這個子串，分別看前1個字元，前2個字元，3個... i個 最後到15個。
第1個a無對稱，所以對稱程度0
前兩個ag無對稱，所以也是0
依次類推前面0-4都一樣是0
最後一個是0～3都一樣是0
前綴next數組的求解演算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字元串長度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推
while( Pattern[i] != Pattern[k] && k!=0 )
k=prefix[k-1]; //繼續遞歸
if( Pattern[i] == Pattern[k])//找到了這個子對稱，或者是直接繼承了前面的對稱性，這兩種都在前面的基礎上++
prefix[i]=k+1;
else
prefix[i]=0; //如果遍歷了所有子對稱都無效，說明這個新字元不具有對稱性，清0
}
}
(10)kmp演算法next擴展閱讀：
設主串（下文中我們稱作T）為：a b a c a a b a c a b a c a b a a b b
模式串（下文中我們稱作W）為：a b a c a b
用暴力演算法匹配字元串過程中，我們會把T[0] 跟 W[0] 匹配，如果相同則匹配下一個字元，直到出現不相同的情況，此時會丟棄前面的匹配信息，然後把T[1] 跟 W[0]匹配，循環進行，直到主串結束，或者出現匹配成功的情況。這種丟棄前面的匹配信息的方法，極大地降低了匹配效率。
而在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。