資料結構與演算法

(9 points) The pseudo code function to compute the prefix function in the Knuth-Morris-Pratt (KMP) string matching algorithm is given below. Given a pattern string $P[1..m]$, the prefix function is $\pi:\{1,2,\dots,m\}\to\{0,1,\dots,m-1\}$ such that $\pi[q]$ is the length of the longest prefix of $P$ that is a proper suffix of $P_q$ (the $q$-character prefix of $P$). For pattern string $P=$ABACABACABACABAD, how many times is line 7 executed?

COMPUTE-PREFIX-FUNCTION(P)
1   m = P.length
2   let π[1..m] be a new array
3   π[1] = 0
4   k = 0
5   for q = 2 to m
6       while k > 0 and P[k+1] ≠ P[q]
7           k = π[k]
8       if P[k+1] == P[q]
9           k = k + 1
10      π[q] = k
11  return π