TY - GEN

T1 - Finding repeats with fixed gap

AU - Kolpakov, R.

AU - Kucherov, G.

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84964461883&partnerID=8YFLogxK

U2 - 10.1109/SPIRE.2000.878192

DO - 10.1109/SPIRE.2000.878192

M3 - Conference contribution

AN - SCOPUS:84964461883

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

SP - 162

EP - 168

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

PB - Institute of Electrical and Electronics Engineers Inc.

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

Y2 - 27 September 2000 through 29 September 2000

ER -