Affiliations: College of Mechanical and Electrical Engineering, China
Jiliang University, Hangzhou Zhejiang 310018, China. E-mail: [email protected] | Department of Computer Science and Engineering,
Zhejiang University Hangzhou Zhejiang 310027, China. E-mail: [email protected] | Department of Computer Science, King's
College London Strand, London WC2R 2LS, England. E-mail: [email protected]
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.
Keywords: the λ-cover problem, the general λ-cover problem, the λ-seed problem, λ-combinations, the Equivalence Class Tree, the Reverses Equivalence Class Tree, String regularities, λ-regularities
