1樓：匿名使用者
就用這個例子：
a b c a a b a b c
前兩位固定是0 1
next[2] 擷取前兩個：a b
比較a b的第一位和最後一位是否相等，等的話為1，不等為0因此next[2]=0+1 (這個加1是固定的)next[3] 擷取前三個 a b c
比較a !=c ,再比較 a b !=b c ，因此還是為0next[3]=0+1=1
next[4] 擷取前四 a b c a
比較a = a ，為1，再看 ab !=ca ,再看 abc !=bca 因此為1
next[4]=1+1=2
next[5]截前五 a b c a a
a = a =>1 , ab !=aa , abc!=caa, abca !=bcaa 因此為1
next[5]=1+1=2
next[6]截前六 a b c a a ba!=b , 0 a b = ab =>2 , abc !=aab, abca !=caab, abcaa!=bcabb
因此為2 next[6]=2+1=3
打得好累。。 演算法就是如上這種。
2樓：網友
kmp我倒是看過，可你寫的我還真是看不懂。。
演算法思想你明白吧？就不用看這個**了麼。
3樓：匿名使用者
t(j+1-k)t(j+2-k)t(j+3-k)..t(j-1)就是指模式串的末k-1個字元。
例中的模式串abcaababc
假設匹配到abcaab都是一樣的，但是第7個字元不一樣了。
這時候由於前面的abcaab是匹配成功的，說明主串這部分也是ab..ab結構。這時候，你就不用再從頭匹配了，可以認為模式串起始的ab與主串中的第二個ab匹配成功，以主串中第2個ab的a算作新的起點1,就可以直接從第3個字元開始匹配。
所以next[7]=3
資料結構關於串的kmp演算法的理解高手請進
4樓：網友
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的不同。一個是通過移動被匹配字串比較字元的指標來實現匹配，一個是移動模式字串的當前比較字元的位置指標來實現匹配。對於匹配串字元回退位置這個計算書中已經很清楚，根據演算法單步除錯一次自然就理解了。
5樓：網友
主要理解next[j]的含義即可，當然還有next函式的改進演算法。
關於kmp演算法的說明有什麼？
6樓：北京理工大學出版社
（1）未改進的模式匹配演算法的時間複雜度為o（nm），但在一般情況下，其實際的執行時間接近o（n＋m），因此至今仍被採用。
（2）kmp演算法僅當模式與主串之間存在許多「部分」匹配的情況下才顯得比未改進的模式匹配快。
（2）kmp演算法的最大特點是指示主串的指標不需要回溯，在整個匹配過程中，對主串僅需要從頭至尾掃描一遍，這對處理儲存在外存上的大檔案是非常有效的。
kmp演算法簡單易懂解釋？或用一個簡單例子逐步說明一下。謝！
7樓：匿名使用者
好吧~kmp當初我也想了挺久的~很巧妙的演算法啊！相必複製百科什麼的你也不會看的了所以我手打吧…下面是我的理解~
為了解說方便我把長的稱為文字串，短的稱為目標串~
常規的匹配演算法是把目標串一位一位地右移，跟文字串比較，而kmp則是跳著右移~
舉幾個例子相信你就懂了。
比如有一目標串為ababaca，當前位置匹配了前5個，也就是匹配了ababa，後面兩個不匹配。
這說明了文字串當前位置也是ababa
顯然右移一位是不行的，因為從目標串可以看出(abab)a與a(baba)括號裡的內容不相等。
而右移兩位是可能可行的~因為可以看出(aba)ba與ab(aba)括號裡的內容是相等的，這意味著移動兩位後，目標串前三位aba是肯定匹配的~因為移動前也匹配~
再舉一個例子~比如有目標串abcab，當前位置匹配了前兩個ab
那麼就需要右移3個位置，因為(ab)cab與abc(ab)括號裡內容相同，移動後有可能會匹配~
懂了麼？表達能力有限…我也不能講得更好了…具體**網上一大堆，《演算法導論》裡面也有~我當初就是在算導裡學會的！
如果懂了，希望有追加分啊，手打累死！！！
不懂的話，追問吧……
C語言資料結構，C語言 資料結構
include include defineinfinity0 definemax vertex num10 最大頂點數 definemax edge num40 最大邊數typedefenumgraphkind typedefcharvertextype 頂點資料型別typedefstructar...
資料結構c語言描述，資料結構（C語言描述）
include include include define datatype int define maxsize 1000 typedef struct nodebitreenode datatype bt maxsize bitreenode buildbtree datatype bt,in...
資料結構（使用C語言）佇列，資料結構C語言佇列執行不了
include stdio.h include malloc.h include stdlib.h include conio.h define max 80 typedef struct seque seque init seque int empty seque seque s int in s...