Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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