login
This site is supported by donations to The OEIS Foundation.

 

Logo


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 iff 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;

}

CROSSREFS

Sequence in context: A039808 A138164 A130802 * A036618 A003018 A196244

Adjacent sequences:  A022540 A022541 A022542 * A022544 A022545 A022546

KEYWORD

nonn,nice

AUTHOR

Dianne Miller (millerdm(AT)mcmaster.ca)

EXTENSIONS

Program and terms a(19) and beyond by 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 22:34 EDT 2018. Contains 316327 sequences. (Running on oeis4.)