Two-pattern strings I—A recognition algorithm

F. Franěk; W. Lu; W.F. Smyth

doi:10.1016/S1570-8667(03)00037-6

Back

Two-pattern strings I—A recognition algorithm

Journal article

Peer reviewed

Two-pattern strings I—A recognition algorithm

F. Franěk, W. Lu and W.F. Smyth

Journal of Discrete Algorithms, Vol.1(5-6), pp.445-460

2003

DOI: https://doi.org/10.1016/S1570-8667(03)00037-6

Files and links (1)

url

Link to Published Version *Subscription may be requiredView

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

Details

Title: Two-pattern strings I—A recognition algorithm
Authors/Creators: F. Franěk (Author/Creator)
W. Lu (Author/Creator)
W.F. Smyth (Author/Creator)
Publication Details: Journal of Discrete Algorithms, Vol.1(5-6), pp.445-460
Publisher: Elsevier
Identifiers: 991005544765407891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

44 Record Views