A179476 Numbers of distinct Knuth-Morris-Pratt arrays of length n.

1, 2, 4, 8, 17, 37, 85, 197, 465, 1106, 2656, 6414, 15582, 38011, 93124, 228927, 564674, 1396860, 3464995, 8616281

Offset

1,2

Links

Table of n, a(n) for n=1..20.

J.-P. Duval, T. Lecroq, and A. Lefebvre. Efficient validation and construction of knuth-morris-pratt arrays. In Conference in honor of Donald E. Knuth, Bordeaux, France, 2007.

Example

For example a string of length 3 can have one of the following 4 KMP arrays: 000, 002, 010, 011.

Crossrefs

Cf. A022543

Sequence in context: A358453 A331783 A003426 * A087803 A212658 A036374

Adjacent sequences: A179473 A179474 A179475 * A179477 A179478 A179479

Keyword

nonn,more

Author

Arnaud Lefebvre (arnaud.lefebvre(AT)univ-rouen.fr), Jul 16 2010

Status

approved