?
讀書筆記終于寫完了，寫一下我對KMP的理解。
KMP的思想就是盡量利用已經得到的信息，來降低時間復雜度，已經得到的信息存放在next數組里。算法確實很難理解，所以很難講解。。舉個例子來說吧。
設字符串是str[]，next[5] = 2。
就表示str[5]前面的2個字符，與str[2]前面的2個字符相同，也就是str[0] == str[3], str[1] == str[4],這樣把str[2]平移到str[5]的位置以后，就能保證前面的已經匹配了。就是下圖：
目標串 ? ?..........a ?b ?c.........
str[] ? a ?b ?c ?a ?b ?d ?e ?f
下標 ? ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7
這時候在下標為5的位置，d和c是不匹配的，因為next[5] = 2，所以把下標為2的c平移到下標為5的位置，再次比較。
目標串 ? ?..........a ?b ?c.........
?? ? ? ? ? ?str[] ? ? ? ? ? ? ?a ?b ?c ?a ?b ?d ?e ?f
下標 ? ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7
當下標超出待匹配的字符串的長度時，就說明在目標串中找到了該字串。
這里還有一個定理：next數組中的值就是"前綴"和"后綴"的最長的共有元素的長度。
還有一句“名言”：假如你要向你喜歡的人表白的話，我的名字是你的告白語中的子串嗎？
最后是幾篇比較好的講解KMP的文章，講解方式各不相同，但是都講得特別好。
http://www.matrix67.com/blog/archives/115
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://blog.csdn.net/v_july_v/article/details/7041827
1 void kmp(char target[], char source[]) 2 { 3 int n = strlen(target); 4 int m = strlen(source); 5 int *next = new int[m]; 6 int j = -1; 7 next[0] = -1; 8 for(int i = 1; i < m; i++) 9 { 10 while(j >= 0 && source[j+1] != source[i]) 11 j = next[j]; 12 if(source[j+1] == source[i]) 13 j++; 14 next[i] = j; 15 } 16 j = -1; 17 for(int i = 0; i < n; i++) 18 { 19 while(j >= 0 && source[j+1] != target[i]) 20 j = next[j]; 21 if(source[j+1] == target[i]) 22 j++; 23 if(j >= m-1) 24 { 25 printf("%d\n", i-m+1); 26 j = next[j]; //繼續查找更多 27 //return; //不再繼續查找 28 } 29 } 30 }
?
)
)
