民國110年 第2梯次 電腦軟體設計(C++)乙級 學科
第9題
利用Knuth-Morris-Pratt 演算法在長度為m 的字串中搜尋長度為n 的字串,所需的時間複雜度(Ti me Complexity)為何?
題目
利用Knuth-Morris-Pratt 演算法在長度為m 的字串中搜尋長度為n 的字串,所需的時間複雜度(Ti me Complexity)為何?
- (1) θ(n)
- (2) θ(m+n )
- (3) θ(mn)
- (4) θ(m)
官方答案
(2) θ(m+n )
解析
KMP（Knuth-Morris-Pratt）字串搜尋演算法先對長度n的模式字串建表（失敗函式/部分符合表），耗時θ(n)；隨後在長度m的文字串中線性掃描比對，因指標不回溯，耗時θ(m)。整體時間複雜度為θ(m+n)，優於暴力法的θ(mn)。因此答案為選項2。需注意m為文字長、n為模式長，兩者皆影響總成本，且KMP的優勢在於避免文字指標回退，使比對維持線性。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。