Back to Search
Start Over
Locating Maximal Multirepeats in Multiple Strings Under Various Constraints†A preliminary version of the results of this paper was presented in CPM 2002.
- Source :
-
Computer Journal . 2007, Vol. 50 Issue 2, p178-185. 8p. - Publication Year :
- 2007
-
Abstract
- A multirepeat in a string is a substring (factor) that appears a predefined number of times. A multirepeat is maximal if it cannot be extended either to the right or to the left and produce a multirepeat. In this paper, we present algorithms for two different versions of the problem of finding maximal multirepeats in a set of strings. In the case of arbitrary gaps, we propose an algorithm with O(σN2n + α) time complexity. When the gap is bounded in a small range c, we propose an algorithm with O((c2 + σ2)mN2n log(Nn) + α) time complexity. Here, N is the number of strings, n the mean length of each string, m the multiplicity of the multirepeat and α the number of reported occurrences. Our results extend previous work by considering sets of strings as well as by generalizing pairs to multirepeats. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*STRING
*MATHEMATICS
*FACTOR analysis
*COMPLEXITY (Philosophy)
*RESEARCH
Subjects
Details
- Language :
- English
- ISSN :
- 00104620
- Volume :
- 50
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Computer Journal
- Publication Type :
- Academic Journal
- Accession number :
- 24324048
- Full Text :
- https://doi.org/10.1093/comjnl/bxl058