教甄◆資訊科技概論專業(電腦科)題庫下載題庫

Knuth-Morris-Pratt (KMP) 字串比較演算法的時間複雜度是 O(M+N)。答案選項 (C) 正確。

KMP 演算法是一種用於在一個主字串中尋找子字串的高效方法。它的時間複雜度基於主要的操作，其中 M 是主字串的長度，N 是要尋找的子字串的長度。

KMP 演算法的核心概念是利用子字串的部分匹配表（Partial Match Table）或稱為失敗函數（Failure Function），它在預處理階段計算並儲存子字串中的部分匹配值。這些值指示著當匹配失敗時，應該跳過主字串中的一些位置，以避免不必要的比較。

在 KMP 演算法的主要迴圈中，主字串和子字串進行比較。當匹配失敗時，KMP 演算法根據部分匹配表的值來決定下一次比較的位置，這樣可以跳過一些比較，減少不必要的操作。因此，它的時間複雜度為 O(M+N)，其中 M 是主字串的長度，N 是子字串的長度。

選項 (A) O(M×N) 表示時間複雜度是主字串長度 M 乘以子字串長度 N，這是不正確的。KMP 演算法通過使用部分匹配表減少了比較操作的數量。

選項 (B) O(M/N) 不正確，因為 M/N 不代表 KMP 演算法的時間複雜度。

選項 (D) O(MN) 表示時間複雜度是主字串長度 M 乘以子字串長度 N，這是不正確的。KMP 演算法通過使用部分匹配表減少了比較操作的數量。

因此，正確答案是選項 (C) O(M+N)。