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

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