Journal article
Two-Pattern strings
Combinatorial Pattern Matching, Vol.2373, pp.76-84
2002
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 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}.
Details
- Title
- Two-Pattern strings
- Authors/Creators
- F. Franěk (Author/Creator) - McMaster-CarrJ. Jiang (Author/Creator) - IBM (Denmark)W. Lu (Author/Creator) - IBM (Denmark)W.F. Smyth (Author/Creator) - Curtin University
- Publication Details
- Combinatorial Pattern Matching, Vol.2373, pp.76-84
- Publisher
- Springer Verlag
- Identifiers
- 991005542946507891
- Copyright
- 2002 Springer-Verlag Berlin Heidelberg
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
148 File views/ downloads
45 Record Views