A022543 Number of distinct 'failure tables' for a string of length n.

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

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