Catalog Home Page

Approximate Periods of Strings

Sim, J.S., Park, K., Iliopoulos, C.S. and Smyth, W.F. (1999) Approximate Periods of Strings. Lecture Notes in Computer Science, 1645 . pp. 123-133.

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 rules.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: Springer Verlag
Copyright: 1999 Springer-Verlag
Notes: Book title: Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99 Warwick University, UK, July 22–24, 1999 Proceedings
Item Control Page Item Control Page