Title: Fast and Practical Algorithms for Computing All the Runs in a String
Abstract: A repetition in a string x is a substring \({ \bf{w}} = {\it \bf{u}}^e\) of x, maximum e ≥ 2, where u is not itself a repetition in w. A run in x is a substring \({\it \bf{w}} = {\it \bf{u}}^e{\it \bf{u^{*}}}\) of "maximal periodicity", where \({\it \bf{u}}^e\) is a repetition and u * a maximum-length possibly empty proper prefix of u. A run may encode as many as \(|{\it \bf{u}}|\) repetitions. The maximum number of repetitions in any string \({\it \bf{x}} = {\it \bf{x}}[1..n]\) is well known to be Θ(nlogn). In 2000 Kolpakov & Kucherov showed that the maximum number of runs in x is O(n); they also described a Θ(n)-time algorithm, based on Farach's Θ(n)-time suffix tree construction algorithm (STCA), Θ(n)-time Lempel-Ziv factorization, and Main's Θ(n)-time leftmost runs algorithm, to compute all the runs in x. Recently Abouelhoda et al. proposed a Θ(n)-time Lempel-Ziv factorization algorithm based on an "enhanced" suffix array — a suffix array together with other supporting data structures. In this paper we introduce a collection of fast space-efficient algorithms for computing all the runs in a string that appear in many circumstances to be superior to those previously proposed.
Publication Year: 2007
Publication Date: 2007-08-13
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 32
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot