Finding Repeats with Fixed Gap

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by R. Kolpakov Articles by G. Kucherov

Seventh International Symposium on String Processing Information Retrieval (SPIRE'00)

A Coru?a, Spain

September 27-September 29

ISBN: 0-7695-0746-8

	ASCII Text	x
	R. Kolpakov, G. Kucherov, "Finding Repeats with Fixed Gap," String Processing and Information Retrieval, International Symposium on, pp. 162, Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), 2000.

	BibTex	x
	@article{ 10.1109/SPIRE.2000.878192, author = {R. Kolpakov and G. Kucherov}, title = {Finding Repeats with Fixed Gap}, journal ={String Processing and Information Retrieval, International Symposium on}, volume = {0}, year = {2000}, isbn = {0-7695-0746-8}, pages = {162}, doi = {http://doi.ieeecomputersociety.org/10.1109/SPIRE.2000.878192}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - String Processing and Information Retrieval, International Symposium on TI - Finding Repeats with Fixed Gap SN - 0-7695-0746-8 SP EP A1 - R. Kolpakov, A1 - G. Kucherov, PY - 2000 KW - string matching; subword occurrence repeats; fixed gap; complexity; output size; occurrence pairs; quasi-squares; strings; searching VL - 0 JA - String Processing and Information Retrieval, International Symposium on ER -

R. Kolpakov, Inst. for Inf. & Appl. Math., Moscow Univ., Russia

G. Kucherov, Inst. for Inf. & Appl. Math., Moscow Univ., Russia

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SPIRE.2000.878192

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.

Index Terms:

string matching; subword occurrence repeats; fixed gap; complexity; output size; occurrence pairs; quasi-squares; strings; searching

Citation:

R. Kolpakov, G. Kucherov, "Finding Repeats with Fixed Gap," spire, pp.162, Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), 2000

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.