HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Finding Repeats With Fixed Gap

Roman Kolpakov 1 Gregory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We propose an algorithm for finding in a word all pairs of occurrences of the same subword within a given distance $r$. The obtained complexity is $O(n\log r +S)$, where $S$ is the size of the output. We also show how the algorithm can be modified in order to find all such pairs of occurrences separated by a given word. The solution uses an algorithm for finding all {\em quasi-squares} in two strings, a problem that generalizes the well-known problem of searching for squares.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 9:11:59 AM
Last modification on : Friday, February 4, 2022 - 3:31:53 AM
Long-term archiving on: : Wednesday, March 29, 2017 - 1:06:05 PM


  • HAL Id : inria-00107855, version 1



Roman Kolpakov, Gregory Kucherov. Finding Repeats With Fixed Gap. 7th International Symposium on String Processing & Information Retrieval - SPIRE 2000, 2000, Coruna, Spain, pp.162--168. ⟨inria-00107855⟩



Record views


Files downloads