Implementing Efficient Algorithms for Computing Runs
Chia-Chun Weng · MacSphere (McMaster University) · 2011
In the first part of this thesis we present a C++ implementation of an improved O(n log n) algorithm to compute runs, number of primitively rooted distinct squares, and maximal repetitions, based on Crochemore's partitioning algorithm. This is a joint work with Mei Jiang and extends her work on the problem. In the second part we present a C++ implementation of a linear algorithm to compute runs based on the Main's, and Kolpakov and Kucherov's algorithms following the strategy: 1. Compute suffix array and LCP array in linear time; 2. Using the suffix array and LCP array, compute Lempel-Ziv factorization in linear time; 3. Using the Lempel-Ziv factorization, compute in linear time some of the runs that include all the leftmost runs following Main's algorithm; 4. Using Kolpakov and Kucherov's approach, compute in linear time the rest of all the runs. For our linear time implementation, we partially relied on Jonathan Fischer's Java implementation.