Generating Necklaces and Strings with Forbidden Substrings

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Joe Sawada, Department of Computer Science, University of Victoria, Canada.

Abstract:

Given a length m string f over a k-ary alphabet and a positive integer n, we develop efficient algorithms to generate

all k-ary strings of length n that have no substring equal to f,
all k-ary circular strings of length n that have no substring equal to f, and
all k-ary necklaces of length n that have no substring equal to f, where f is an aperiodic necklace.

Each of the algorithms runs in amortized time O(1) per string generated, independent of k, m, and n.

Presented at the 6th Annual International Combinatorics and Computing Conference (COCOON), Bondi Beach, Australia, Lecture Notes in Computer Science, #1858 (2000) 330-339.
Selected Citations to this paper:
- P. Flener and J. Pearson, Solving Necklace Constraint Problems, Journal of Algorithms: Cognition, Informatics and Logic, to appear, 2008.

Back to list of publications.