Catalog Home Page

Approximate periods of strings

Sim, J.S., Iliopoulos, C.S., Park, K. and Smyth, W.F. (2001) Approximate periods of strings. Theoretical Computer Science, 262 (1-2). pp. 557-568.

PDF - Authors' Version
Download (271kB)
Link to Published Version:
*Subscription may be required


The study of approximately periodic strings is relevant to diverse applications such as molecular biology, data compression, and computer-assisted music analysis. Here we study different forms of approximate periodicity under a variety of distance functions. We consider three related problems, for two of which we derive polynomial-time algorithms; we then show that the third problem is NP-complete.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2001 Elsevier Science B.V.
Item Control Page Item Control Page


Downloads per month over past year