演算法›Ch6 KMP 字串比對第 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 , the prefix function for the pattern is the function . What is for the following pattern ?
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| a | b | a | b | a | b | a | b | c | a |
(A) 4 (B) 5 (C) 6 (D) 7
參考答案與解析
答案 (B) 5。P=ababababca,逐步計算前綴函數:π[1]=0;π[2](b vs a)=0;π[3](a match P[1])=1;π[4](b match P[2])=2;π[5](a match P[3])=3;π[6](b match P[4])=4;π[7](a match P[5])=5。
📄 台大110
▤完整推導請見《WH 資工筆記 · 演算法》Ch6 KMP 字串比對