The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A022543 Number of distinct 'failure tables' for a string of length n. 1
 1, 2, 4, 9, 20, 47, 110, 263, 630, 1525, 3701, 9039, 22140, 54460, 134339, 332439, 824735, 2051307, 5113298, 12773067, 31968041, 80152901, 201297338, 506324357, 1275385911, 3216901194, 8124150323, 20541362001, 51994801119, 131747424892 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 REFERENCES Knuth-Morris-Pratt pattern matching algorithm. LINKS Table of n, a(n) for n=1..30. Dennis Moore, W. F. Smyth and Dianne Miller, Counting distinct strings, Algorithmica, Vol. 23 (1999), 1-13. EXAMPLE For example, a string of length 3 can have one of the following 4 'failure tables': 012, 001, 010, 000. PROG (C++) // check(p, n) returns true if and only if there exists a string of length n that have provided failure table (assuming that p[0] == -1). bool check(int *p, int n) { static int a[64]; for (int i = 0; i <= n; i++) a[i] = i; for (int i = 1, k = 0; i <= n; i++) { for (; k >= p[i]; k = p[k]); if (++k != p[i]) return false; if (k) a[i] = a[k]; } for (int i = 1, k = 0; i <= n; i++, k++) for (; k >= p[i]; k = p[k]) if (k + 1 < i && a[k + 1] == a[i]) return false; return true; } // count(n) returns number of different failure tables for string of length n. long long count(int n, int i = 1) { static int p[64] = {-1}; if (!check(p, i - 1)) return 0; if (i > n) return 1; long long result = 0; for (p[i] = 0; p[i] <= p[i - 1] + 1; p[i]++) result += count(n, i + 1); return result; } // Pavel Irzhavski, Feb 25 2014 CROSSREFS Sequence in context: A039808 A138164 A130802 * A307557 A036618 A349014 Adjacent sequences: A022540 A022541 A022542 * A022544 A022545 A022546 KEYWORD nonn,nice AUTHOR Dianne Miller (millerdm(AT)mcmaster.ca) EXTENSIONS a(19) and beyond from Pavel Irzhavski, Feb 25 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 23 06:04 EDT 2024. Contains 371906 sequences. (Running on oeis4.)