熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第四章 答案[9]

2013-11-15 14:57:41  來源: 數據結構 

  .()p的nextval函數值為(p的next函數值為

  ()利用KMP(改進的nextval)算法每趟匹配過程如下

  第一趟匹配 abcaabbabcabaacbacba
  abcab(i=j=)
  第二趟匹配 abcaabbabcabaacbacba
  abc(i=j=)
  第三趟匹配 abcaabbabcabaacbacba
  a(i=j=)
  第四趟匹配 abcaabbabcabaac bacba
  (成功)             abcabaa(i=j=)

  .KMP算法的時間復雜性是O(m+n)

  p的next和nextval值分別為

  .()p的nextval函數值為(next函數值為

  ()利用所得nextval數值手工模擬對s的匹配過程與上面題類似為節省篇幅故略去

  .模式串T的next和nextval值分別為

  .第行的p[J]=p[K]語句是測試模式串的第J個字符是否等於第K個字符如是則指針J和K均增加繼續比較行的p[J]=p[K]語句的意義是當第J個字符在模式匹配中失配時若第K個字符和第J個字符不等則下個與主串匹配的字符是第K個字符;否則若第K個字符和第J個字符相等則下個與主串匹配的字符是第K個字符失配時的下一個(即NEXTVAL[K])

  該算法在最壞情況下的時間復雜度O(m

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22608.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.