Content-Length: 251162 | pFad | http://github.com/cp-algorithms/cp-algorithms/issues/963

57 Question about article "Prefix function - Knuth-Morris-Pratt" · Issue #963 · cp-algorithms/cp-algorithms · GitHub
Skip to content

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

@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









    ApplySandwichStrip

    pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


    --- a PPN by Garber Painting Akron. With Image Size Reduction included!

    Fetched URL: http://github.com/cp-algorithms/cp-algorithms/issues/963

    Alternative Proxies:

    Alternative Proxy

    pFad Proxy

    pFad v3 Proxy

    pFad v4 Proxy