Two-pattern strings I—A recognition algorithm

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