回覆列表
  • 1 # 局阿如竇娥特

     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

  • 中秋節和大豐收的關聯?
  • 憐憫的名人名言有哪些?