Catalog Home Page

Two-pattern strings I—A recognition algorithm

Franěk, F., Lu, W. and Smyth, W.F. (2003) Two-pattern strings I—A recognition algorithm. Journal of Discrete Algorithms, 1 (5-6). pp. 445-460.

Link to Published Version: http://dx.doi.org/10.1016/S1570-8667(03)00037-6
*Subscription may be required

Abstract

This paper introduces a new class of strings on {a,b}, called two-pattern strings, that constitute a substantial generalization of Sturmian strings while at the same time sharing many of their nice properties. In particular, we show in this paper that two-pattern strings can be recognized in time proportional to their length. This result is a prelude to showing that the repetitions in these substrings can also be computed in linear time, further that two-pattern strings occur in some sense frequently in the class of all strings on {a,b}.

Publication Type: Journal Article
Publisher: Elsevier
Copyright: © 2003 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27929
Item Control Page Item Control Page