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

Franěk, F., Jiang, J., Lu, W. and Smyth, W.F. (2002) Two-Pattern strings. Lecture Notes in Computer Science, 2373 . pp. 76-84.

PDF - Authors' Version
Download (287kB)
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 that, in common with Sturmian strings, only time linear in the string length is required to recognize a two-pattern string as well as to compute all of its repetitions. We also show that two-pattern strings occur in some sense frequently in the class of all strings on {a,b}.

Item Type: Journal Article
Publisher: Springer Verlag
Copyright: 2002 Springer-Verlag Berlin Heidelberg
Item Control Page Item Control Page


Downloads per month over past year