第 一 題

「失敗函數（failure function）$f(j)$」指在 KMP 演算法中，針對樣式字串（Pattern）$P = p_0 p_1 ... p_{m-1}$ 預先計算的函數。其代表在子字串 $P[0..j]$ 中，使得「真前綴與真後綴完全相同」的最大真前綴之最後一個字元的索引。 數學定義為： $$ f(j) = \begin{cases} \max { k \mid k < j \text{ 且 } p_0 p_1 ... p_k = p_{j-k} p_{j-k+1} ... p_j } & \text{若此 } k \text{ 存在} \ -1 & \text{若無此 } k \text{ 存在} \end{cases} $$

【解題關鍵】Failure Function F(j) 定義為子字串 pattern[0...j] 中，最長相同真前綴與真後綴的長度減 1（Horowitz 定義）。 【解答】 逐步推導：

【解題思路】利用 KMP 演算法中的 Failure Function（失敗函數），計算已匹配字串的最長相同前綴與後綴長度，以決定下一次比對的起點。 【詳解】 已知：