A393101 Number of character comparisons needed by Knuth-Morris-Pratt string search to identify the first occurrence of string n in the infinite Champernowne word 123456789101112... (A033307).

1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 2, 22, 25, 28, 31, 34, 37, 40, 33, 17, 35, 3, 46, 49, 52, 55, 58, 61, 54, 19, 40, 57, 4, 70, 73, 76, 79, 82, 75, 21, 42, 63, 79, 5, 94, 97, 100, 103, 96, 23, 44, 65, 86, 101, 6, 118, 121, 124, 117, 25, 46, 67, 88, 109, 123, 7

Offset

1,2

Comments

The comparisons counted are those between the pattern and text, initial comparisons of the pattern with itself are not counted.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..1000

Michael S. Branicky, Python program for OEIS A393101

Sean A. Irvine, Java program (github)

Wikipedia, Knuth-Morris-Pratt algorithm

Prog

(Python) # see linked program

Crossrefs

Cf. A033307, A022543, A392989, A390503, A387487.

Sequence in context: A143265 A109841 A174234 * A163807 A118766 A136399

Adjacent sequences: A393098 A393099 A393100 * A393102 A393103 A393104

Keyword

nonn,base

Author

Sean A. Irvine, Feb 01 2026

Status

approved