String / Substring (Bibtex)

P309: Enumeration of all $k$-ary strings of length $n$ that have no substring equal to $f$

Input:

A $k$-ary string $f$ with length $m$, and a positive integer $n$.

Output:

All $k$-ary strings of length $n$ that have no substring equal to $f$.

Complexity:

$O(1)$ time per string.

Comment:

Reference:

[Ruskey2000a] (Bibtex)

P310: Enumeration of all circular $k$-ary strings of length $n$ that have no substring equal to $f$

Input:

A $k$-ary string $f$ with length $m$, and a positive integer $n$.

Output:

All circular $k$-ary strings of length $n$ that have no substring equal to $f$.

Complexity:

$O(1)$ time per string.

Comment:

Reference:

[Ruskey2000a] (Bibtex)

P311: Enumeration of all $k$-ary necklaces of length $n$ that have no substring equal to $f$

Input:

A $k$-ary string $f$ with length $m$, and a positive integer $n$.

Output:

All $k$-ary necklaces of length $n$ that have no substring equal to $f$.

Complexity:

$O(1)$ time per string.

Comment:

$f$ is an aperiodic necklace.

Reference:

[Ruskey2000a] (Bibtex)