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.
*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.
|Publication Type:||Journal Article|
|Notes:||Book title: Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99 Warwick University, UK, July 22–24, 1999 Proceedings|
|Item Control Page|