Open
Description
Article: Prefix function - Knuth-Morris-Pratt
Problem:
Under the section "Compressing a string" the following claim is made:
Now consider the second block of the string. Since the prefix is equal with the suffix, and both the prefix and the suffix cover this block and their displacement relative to each other $k$ does not divide the block length $p$ (otherwise $k$ divides $n$ ), then all the characters of the block have to be identical.
I'm not sure I see the leap to the bolded conclusion (for example, suppose p = 8
and k = 6
). Am I missing something or is it rather that the blocks decompose into repeating blocks of the gcd of p
and k
(which might not always be 1)?