卷別

資料結構與演算法

選擇

國立臺灣大學 2026 · 考試 · 第 8 題

(4 points) Given the string $S = \texttt{wuwvwuuv}$ , compute the Knuth–Morris–Pratt failure function $\pi[0 \dots 7]$ , where $\pi[i]$ is the length of the longest proper prefix of $S[0 \dots i]$ which is also a suffix of $S[0 \dots i]$ . Which of the following is correct?

(A)
$\pi = [0, 0, 1, 0, 1, 2, 0, 0]$
(B)
$\pi = [0, 0, 1, 0, 1, 2, 2, 3]$
(C)
$\pi = [0, 1, 0, 1, 2, 0, 1, 2]$
(D)
$\pi = [0, 0, 0, 1, 1, 2, 3, 3]$
(E)
$\pi = [0, 0, 1, 1, 2, 2, 2, 3]$

標準解析

AI 已複查