演算法›Ch6 KMP 字串比對
第 3 題/共 3 題
◀ AL 3/3
3. KMP、Prefix Function
#AL-06-003易KMPPrefix Function

The Knuth-Morris-Pratt (KMP) algorithm is a string-matching algorithm. Its core is the prefix function. Given a pattern P[1..m]P[1..m], the prefix function for the pattern PP is the function π:{1,2,…,m}→{0,1,…,m−1}\pi:\{1,2,\ldots,m\}\to\{0,1,\ldots,m-1\}. What is π[7]\pi[7] for the following pattern PP?

ii12345678910
P[i]P[i]ababababca

(A) 4 (B) 5 (C) 6 (D) 7

📄 台大110
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch6 KMP 字串比對
本章題號 · 1–3 / 3