高99資料結構 - 考試

※ 引述《davchou (davchou)》之銘言：
: [考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處
: 關於字串樣式比對（string pattern matching），最簡單的方法是使用窮舉樣式比對法
: （
: exhaustive pattern matching），此即將樣式（pattern
: ）的字元逐一比較本文（text）的字元，若不對則移下一字元繼續比對，直到比對成功或
: 本文剩下的字元
: 數目少於樣式長度。
: 
: 假設本文是：
: THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED
: ，欲找尋的樣式（pattern）為GENTLE，問：
: 1.總共比較多少次？（5分）
: 本文47 字,pattern 6
: 47-6+1=42
47-6+1=42
窮舉樣式比對要從第一個字元開始一個字元一個字元比
最後一次比對為SPEED前面的_,因為小於六個字就結束
: 2.一共比較多少個字元？（5分）
: 42次比較中,pattern 比較6個字元 = 42*6= 252
: 解答寫43,請問我哪裡想錯嗎?
比對第一個字元G不一樣就不再比第二個字元了 本文中只有一個G需要比對
而比對第二個字發現不符合 所以為42+1=43
: 假設本文是一千個"0"，欲找尋的樣式（pattern）為01010，請問：
: 1.總共比較多少次？（5分）1000-5+1=996
: 2.一共比較多少個字元？（5分）
: 解答寫1992
1. 同理 比對字串為5個字 本文小於五字不比 1000-5+1=996
2.996*2(比對第二字元發現不合)= 1992
: 請問可以解釋,第2小題的答案怎算嗎?

--