(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 for this pattern $P$ is the function $\pi: \{1,2,\ldots,m\} \to \{0,1,\ldots,m-1\}$ such that $\pi[q]$ is the length of the longest prefix of $P$ that is a proper suffix of $P_q$, where $P_q$ denotes the $q$-character prefix of the string $P$. For pattern string $P=$ABACABACABACABAD, how many times is line 7 executed? (Note: only the final answer will be graded and only fully correct answer will be given points)

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