|
%I #34 Dec 15 2018 04:33:34
%S 1,2,4,9,20,47,110,263,630,1525,3701,9039,22140,54460,134339,332439,
%T 824735,2051307,5113298,12773067,31968041,80152901,201297338,
%U 506324357,1275385911,3216901194,8124150323,20541362001,51994801119,131747424892
%N Number of distinct 'failure tables' for a string of length n.
%D Knuth-Morris-Pratt pattern matching algorithm.
%H Dennis Moore, W. F. Smyth and Dianne Miller, <a href="http://www.dcss.mcmaster.ca/~bill/pubs.shtml">Counting distinct strings</a>, <a href="http://link.springer.de/link/service/journals/00453/tocs/02301.html">Algorithmica</a>, Vol. 23 (1999), 1-13.
%e For example, a string of length 3 can have one of the following 4 'failure tables': 012, 001, 010, 000.
%o (C++)
%o // 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).
%o bool check(int *p, int n) {
%o static int a[64];
%o for (int i = 0; i <= n; i++)
%o a[i] = i;
%o for (int i = 1, k = 0; i <= n; i++) {
%o for (; k >= p[i]; k = p[k]);
%o if (++k != p[i])
%o return false;
%o if (k)
%o a[i] = a[k];
%o }
%o for (int i = 1, k = 0; i <= n; i++, k++)
%o for (; k >= p[i]; k = p[k])
%o if (k + 1 < i && a[k + 1] == a[i])
%o return false;
%o return true;
%o }
%o // count(n) returns number of different failure tables for string of length n.
%o long long count(int n, int i = 1) {
%o static int p[64] = {-1};
%o if (!check(p, i - 1))
%o return 0;
%o if (i > n)
%o return 1;
%o long long result = 0;
%o for (p[i] = 0; p[i] <= p[i - 1] + 1; p[i]++)
%o result += count(n, i + 1);
%o return result;
%o } // _Pavel Irzhavski_, Feb 25 2014
%K nonn,nice
%O 1,2
%A Dianne Miller (millerdm(AT)mcmaster.ca)
%E a(19) and beyond from _Pavel Irzhavski_, Feb 25 2014
| 