Three Does Not Divide
A classic use of the prefix function: to find the shortest string t such that s is t repeated a whole number of times, compute k = n - pi[n-1]. If k divides n, the answer is k, otherwise the answer is n.
For s = "abcabcab" the prefix function is
i : 0 1 2 3 4 5 6 7
s[i] : a b c a b c a b
pi[i] : 0 0 0 1 2 3 4 5
What is the length of the shortest t?
Sign in to answer questions and track your progress
Sign In