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

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

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

  .()當模式串中第一個字符與主串中某字符比較不等(失配)時next[]=表示模式串中已沒有字符可與主串中當前字符s[i]比較主串當前指針應後移至下一字符再和模式串中第一字符進行比較

  ()當主串第i個字符與模式串中第j個字符失配時若主串i不回溯則假定模式串第k個字符與主串第i個字符比較k值應滿足條件<k<j並且p1…pk=pjk+…pj即k為模式串向後移動的距離k值有多個為了不使向右移動丟失可能的匹配k要取大由於max{k}表示移動的最大距離所以取max{k}k的最大值為j

  ()在上面兩種情況外發生失配時主串指針i不回溯在最壞情況下模式串從第個字符開始與主串第i個字符比較以便不致丟失可能的匹配

  .這裡失敗函數f即是通常講的模式串的next函數其定義見本章應用題的第

  進行模式匹配時若主串第i個字符與模式串第j個字符發生失配主串指針i不回溯和主串第i個字符進行比較的是模式串的第next[j]個字符模式串的next函數值只依賴於模式串和主串無關可以預先求出

  該算法的技術特點是主串指針i不回溯在經常發生部分匹配和主串很大不能一次調入內存時優點特別突出

  .失敗函數(即next)的值只取決於模式串自身若第j個字符與主串第i個字符失配時假定主串不回溯模式串用第k(即next[j])個字符與第i個相比 p…pk=pjk+…pj為了不因模式串右移與主串第i個字符比較而丟失可能的匹配對於上式中存在的多個k值應取其中最大的一個這樣因jk最小即模式串向右滑動的位數最小避免因右移造成的可能匹配的丟失

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


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