Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.8k
Open
Labels
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, supposep = 8
andk = 6
). Am I missing something or is it rather that the blocks decompose into repeating blocks of the gcd ofp
andk
(which might not always be 1)?