Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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:
*Subscription may be required


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}.

Item Type: Journal Article
Publisher: Elsevier
Copyright: © 2003 Elsevier B.V.
Item Control Page Item Control Page