KMP算法實現代碼

g3mc 9年前發布 | 2K 次閱讀 C/C++

在文章里只給出了算法代碼以及解釋，后邊的留下了一份中文一份英文的參考博文地址以便深刻理解KMP算法。ps：中文的親測，解釋原理簡單易懂。

KMP算法

算法思想

相比蠻力算法，KMP算法預先計算出了一個哈希表，用來指導在匹配過程中匹配失敗后嘗試下次匹配的起始位置，以此避免重復的讀入和匹配過程。這個哈希表被叫做“部分匹配值表(Particial match table)”，它的設計是算法精妙之處。

部分匹配值表

要理解部分匹配值表，就得先了解字符串的前綴(prefix)和后綴(postfix)。

前綴:除字符串最后一個字符以外的所有頭部串的組合。
后綴：除字符串第一個字符以外的所有尾部串的組合。
部分匹配值：一個字符串的前綴和后綴中最長共有元素的長度。
舉例說明：字符串ABCAB

前綴：{A， AB， ABC， ABCA}
后綴：{BCAB， CAB， AB， B}
部分匹配值：2 （AB）
而所謂的部分匹配值表，則為模式串的所有前綴以及其本身的部分匹配值。
還是針對字符串ABCAB，它的部分匹配值表為： 
    A B C A B  
    0 0 0 1 2

算法代碼 

    public static int[] next;  

        public static boolean kmp(String str, String dest) {  
             for (int i = 0, j = 0; i < str.length(); i ++) {  
                   while (j > 0 && str.charAt(i) != dest.charAt(j))//iterate to find out the right next position  
                        j = next[j - 1];  

                   if (str.charAt(i) == dest.charAt(j))  
                        j ++;  

                   if (j == dest.length())  
                        return true;  
              }  
              return false;  
         }  

         public static int[] kmpNext(String str) {  
              int[] next = new int[str.length()];  
              next[0]  = 0;  
              for (int i = 1, j = 0; i < str.length(); i ++) {//j == 0 means the cursor points to nothing.  
                   //the j here stands for the number of same characters for postfix and prefix, instead of  
                   //the index of the end of prefix.  
                    while (j > 0 && strt.charAt(j) != sr.charAt(i))  
                        j = next[j - 1]; //watch out here! it's j - 1 here, instead of j  

                   if (str.charAt(i) == str.charAt(j))  
                        j ++;  

                   next[i] = j;  
              }  
              return next;  
         }

 本文由用戶 g3mc 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！