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

　　四．應用題

　　１．串是零個至多個字符組成的有限序列從數據結構角度講串屬於線性結構與線性表的特殊性在於串的元素是字符

　　２．空格是一個字符其ASCII碼值是空格串是由空格組成的串其長度等於空格的個數空串是不含任何字符的串即空串的長度是零

　　３．最優的T(mn)是O（n）串S是串S的子串且在S中的位置是開始求出最大公共子串的長度恰是串S的長度一般情況下T(mn) =O(m*n)

　　４．樸素的模式匹配（Brute－Force）時間復雜度是Ｏ（m＊n）KMP算法有一定改進時間復雜度達到Ｏ（m＋n）本題也可采用從後面匹配的方法即從右向左掃描比較６次成功另一種匹配方式是從左往右掃描但是先比較模式串的最後一個字符若不等則模式串後移;若相等再比較模式串的第一個字符若第一個字符也相等則從模式串的第二個字符開始向右比較直至相等或失敗若失敗模式串後移再重復以上過程按這種方法本題比較次成功

　　５．KMP算法主要優點是主串指針不回溯當主串很大不能一次讀入內存且經常發生部分匹配時KMP算法的優點更為突出

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22621.html