Skip to content

Question about article "Prefix function - Knuth-Morris-Pratt" #963

Open
@tbobo

Description

@tbobo

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)?

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions