Algorithms for Computing the λ-regularities in Strings
Hui Zhang, Qing Guo, Costas S. Iliopoulos · Fundamenta Informaticae · 2008
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.