Finding repeats with fixed gap

R. Kolpakov, G. Kucherov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

40 Citations (Scopus)

Abstract

We propose an algorithm for finding, within 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 quasi-squares in two strings, a problem that generalizes the well-known problem of searching for squares.

Original languageEnglish
Title of host publicationProceedings - 7th International Symposium on String Processing and Information Retrieval, SPIRE 2000
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages162-168
Number of pages7
ISBN (Electronic)0769507468, 9780769507460
DOIs
Publication statusPublished - 2000
Externally publishedYes
Event7th International Symposium on String Processing and Information Retrieval, SPIRE 2000 - A Curuna, Spain
Duration: 27 Sep 200029 Sep 2000

Publication series

NameProceedings - 7th International Symposium on String Processing and Information Retrieval, SPIRE 2000

Conference

Conference7th International Symposium on String Processing and Information Retrieval, SPIRE 2000
Country/TerritorySpain
CityA Curuna
Period27/09/0029/09/00

Cite this