Prefix function and Z-function

Questions 1 to 5 of 8

1. 1. The prefix function of abacaba is one of the lists below. Which one is correct?

   0 1 2 3 0 1 20 0 1 0 1 2 37 0 1 0 3 0 10 0 1 0 1 2 2
2. 2. A teammate says: "The prefix function loop is linear, because each outer step runs the while loop at most once." Which correction is the strongest?

   The claim is correct, since k grows by at most one per outer step.The function is quadratic on strings such as aaaa, because each pi value is recomputed from the start of the string.One outer step can run the while loop many times. The O(n) bound is amortised: k rises by at most one per step, and each drop of k is paid for by an earlier rise.The loop is linear only when the alphabet has two letters.
3. 3. Which statements about the prefix array pi and the Z-array z are true? Select all that apply.

   Pick every answer that is true.

   pi[i] is the length of the longest proper border of the prefix that ends at i.z[i] is the LCP of the whole string and the suffix that starts at i.pi[i] is never larger than i.z[0] is 0 by convention, so the whole string does not count as a match.Both arrays can be built in O(n) time.
4. 4. What value must z[0] have before the main loop starts, for a string of length n? Write it as a formula.

   Type your answer.

5. 5. The string is abacaba. How many proper borders does the whole string have? Count every border, not only the longest one.

   Type a number.