百度空間 | 百度首頁 | 登錄                  電腦知識擂臺一起學習，一起進步。 主頁博客相冊|個人檔案 |好友   查看文章    
貼]KMP算法中nextval的計算方法2009-03-23 10:00
KMP算法即Knuth-Morris-Pratt算法，是模式匹配的一種改進算法，因為是名字中三人同時發現的，所以稱為KMP算法。因為偶然接觸到有關KMP的問題，所以上網查了一下next數組和nextval數組的求法，卻沒有找到，只有在CSDN的資料文件里找到了next數組的簡單求法（根據書上提供的程序也可以求到，但一般在課堂講解的時候，學生難以理解，所以希望以更容易理解的形式來講解），那位高人說時間關系，先講到這里，于是講完了next數組就功成身退了。BS的同時，自己研究了下nextwal數組，發現了其中的簡易規律，并寫了出來，希望能對需要快速理解KMP中nextval的求法的朋友有所幫助。
     int get_nextval(SString T,int &nextval[ ]){
         //求模式串T的next函數修正值并存入數組nextval。
         i=1; nextval[1]=0; j=0;
         while(i<T[0]){
             if(j==0||T[i]==T[j]){
                 ++i;++j;
                 if (T[i]!=T[j]) nextval[i]=j;
                 else nextval[i]=nextval[j];
             }
             else j=nextval[j];
         }
     }//get_nextval
     根據這段程序來求nextval的值是可以方便計算出來，但如果是應付考研試題或者期末考試就有點麻煩了。而如果記住我推薦的方法，那么任何時候都可以很方便地求解nextval了。
     首先看看next數組值的求解方法。
     例如： 模式串 a b a a b c a c 
   next值 0 1 1 2 2 3 1 2 
   nextval值         
     next數組的求解方法是：第一位的next值為0，第二位的next值為1，后面求解每一位的next值時，根據前一位進行比較。首先將前一位與其next值對應的內容進行比較，如果相等，則該位的next值就是前一位的next值加上1；如果不等，向前繼續尋找next值對應的內容來與前一位進行比較，直到找到某個位上內容的next值對應的內容與前一位相等為止，則這個位對應的值加上1即為需求的next值；如果找到第一位都沒有找到與前一位相等的內容，那么需求的位上的next值即為1。
     看起來很令人費解，利用上面的例子具體運算一遍。
     1.前兩位必定為0和1。
     2.計算第三位的時候，看第二位b的next值，為1，則把b和1對應的a進行比較，不同，則第三位a的next的值為1，因為一直比到最前一位，都沒有發生比較相同的現象。
     3.計算第四位的時候，看第三位a的next值，為1，則把a和1對應的a進行比較，相同，則第四位a的next的值為第三位a的next值加上1。為2。因為是在第三位實現了其next值對應的值與第三位的值相同。
     4.計算第五位的時候，看第四位a的next值，為2，則把a和2對應的b進行比較，不同，則再將b對應的next值1對應的a與第四位的a進行比較，相同，則第五位的next值為第二位b的next值加上1，為2。因為是在第二位實現了其next值對應的值與第四位的值相同。
     5.計算第六位的時候，看第五位b的next值，為2，則把b和2對應的b進行比較，相同，則第六位c的next值為第五位b的next值加上1，為3，因為是在第五位實現了其next值對應的值與第五位相同。
     6.計算第七位的時候，看第六位c的next值，為3，則把c和3對應的a進行比較，不同，則再把第3位a的next值1對應的a與第六位c比較，仍然不同，則第七位的next值為1。
     7.計算第八位的時候，看第七位a的next值，為1，則把a和1對應的a進行比較，相同，則第八位c的next值為第七位a的next值加上1，為2，因為是在第七位和實現了其next值對應的值與第七位相同。
     在計算nextval之前要先弄明白，nextval是為了彌補next函數在某些情況下的缺陷而產生的，例如主串為“aaabaaaab”、模式串為“aaaab”那么，比較的時候就會發生一些浪費的情況：比較到主串以及模式串的第四位時，發現其值并不相等，據我們觀察，我們可以直接從主串的第五位開始與模式串進行比較，而事實上，卻進行了幾次多余的比較。使用nextval可以去除那些不必要的比較次數。
     求nextval數組值有兩種方法，一種是不依賴next數組值直接用觀察法求得，一種方法是根據next數組值進行推理，兩種方法均可使用，視更喜歡哪種方法而定。
     我們使用例子“aaaab”來考查第一種方法。
     1.試想，在進行模式匹配的過程中，將模式串“aaaab”與主串進行匹配的時候，如果第一位就沒有吻合，即第一位就不是a，那么不用比較了，趕快挪到主串的下一位繼續與模式串的第一位進行比較吧，這時，模式串并沒有發生偏移，那么，模式串第一位a的nextval值為0。
     2.如果在匹配過程中，到第二位才發生不匹配現象，那么主串的第一位必定是a，而第二位必定不為a，既然知道第二位一定不為a，那么主串的第一、二兩位就沒有再進行比較的必要，直接跳到第三位來與模式串的第一位進行比較吧，同樣，模式串也沒有發生偏移，第二位的nextval值仍然為0。
     3.第三位、第四位類似2的過程，均為0。
     4.如果在匹配過程中，直到第五位才發生不匹配現象，那么主串的第一位到第四位必定為a，并且第五位必定不為b，可是第五位仍然有可能等于a。如果萬一第五位為a，那么既然前面四位均為a，所以，只要第六位為b，第一個字符串就匹配成功了。所以，現在的情況下，就是看第五位究竟是不是a了。所以發生了下面的比較： 
1 2 3 4 5 6 
a a a a * * 
a a a a b  
 a a a a b 


     前面的三個a都不需要進行比較，只要確定主串中不等于b的那個位是否為a，即可以進行如下的比較：如果為a，則繼續比較主串后面一位是否為b；如果不為a，則此次比較結束，繼續將模式串的第一位去與主串的下一位進行比較。由此看來，在模式串的第五位上，進行的比較偏移了4位（不進行偏移，直接比較下一位為0），故第五位b的nextval值為4。
     我們可以利用第一個例子“abaabcac”對這種方法進行驗證。
     a的nextval值為0，因為如果主串的第一位不是a，那么沒有再比較下去的必要，直接比較主串的第二位是否為a。如果比較到主串的第二位才發生錯誤，則主串第一位肯定為a，第二位肯定不為b，此時不能直接跳到第三位進行比較，因為第二位還可能是a，所以對主串的第二位再進行一次比較，偏移了1位，故模式串第二位的nextval值為1。以此類推，nextval值分別為：01021302。其中第六位的nextval之所以為3，是因為，如果主串比較到第六位才發生不匹配現象，那么主串的前五位必定為“abaab”且第六位必定不是“c”，但第六位如果為“a”的話，那么我們就可以從模式串的第四位繼續比較下去。所以，這次比較為： 1 2 3 4  5 6 7 8 9 10  11  12 
a b a a b * * * * * * * 
   a b a a b c a c  

     而不是： 1 2 3 4  5 6 7 8 9 10  11  12 
a b a a b * * * * * * * 
     a b a a b c a 

     因為前兩位a和b已經確定了，所以不需要再進行比較了。所以模式串第六位的nextval值為這次比較的偏移量3。
     再來看求nextval數組值的第二種方法。
模式串 a b a a b c a c 
next值 0 1 1 2 2 3 1 2 
nextval值 0 1 0 2 1 3 0 2 

     1.第一位的nextval值必定為0，第二位如果于第一位相同則為0，如果不同則為1。
     2.第三位的next值為1，那么將第三位和第一位進行比較，均為a，相同，則，第三位的nextval值為0。
     3.第四位的next值為2，那么將第四位和第二位進行比較，不同，則第四位的nextval值為其next值，為2。
     4.第五位的next值為2，那么將第五位和第二位進行比較，相同，第二位的next值為1，則繼續將第二位與第一位進行比較，不同，則第五位的nextval值為第二位的next值，為1。
     5.第六位的next值為3，那么將第六位和第三位進行比較，不同，則第六位的nextval值為其next值，為3。
     6.第七位的next值為1，那么將第七位和第一位進行比較，相同，則第七位的nextval值為0。
     7.第八位的next值為2，那么將第八位和第二位進行比較，不同，則第八位的nextval值為其next值，為2。
     在“aaaab”內進行驗證。 模式串 a a a a b 
next值 0 1 2 3 4 
nextval值 0 0 0 0 4 

 

類別：數據結構 | 添加到搜藏 | 瀏覽(21) | 評論 (0)  上一篇：右鍵單擊桌面顯示屬性選項卡不見...    下一篇：學好嵌入式 step by step 最近讀者： 登錄后，您就出現在這里。   
    qianru073  
 網友評論：    發表評論：姓　名：     注冊 | 登錄 *姓名最長為50字節 
   
網址或郵箱：  (選填) 
   
內　容： 插入表情  ▼ 閃光字 
 
 
  
   
驗證碼：  
看不清?  
      取消回復 

      

?2009 Baidu