Algorithms for Computing the λ-regularities in Strings

Abstract

We introduce the notion of λ-regularities in strings that consist of λ-covers and λ-seeds, and study three λ-regularities problems – the λ-cover problem, the general λ-cover problem and the λ-seed problem in this paper. λ-regularities can be viewed as generalized string regularities in the sense that a set of λ repetitive strings rather than a single repeated string are considered.

We first present a general algorithm for computing all the λ-combinations of a given string, since they serve as candidates for both λ-covers and λ-seeds. The running time of this algorithm is O(n ^2 ). Relying on this result, we answer the above mentioned three problems all in O(n ^2 ) time.