Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

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

Open
Assignees
adamant-pwn
Labels
@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, 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)?

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions


    [8]ページ先頭

    ©2009-2025 Movatter.jp