<p>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:</p> <p>1. Compute suffix array and LCP array in linear time;</p> <p>2. Using the suffix array and LCP array, compute Lempel-Ziv factorization in linear time;</p> <p>3. Using the Lempel-Ziv factorization, compute in linear time some of the runs that include all the leftmost runs following Main's algorithm;</p> <p>4. Using Kolpakov and Kucherov's approach, compute in linear time the rest of all the runs.</p> <p>For our linear time implementation, we partially relied on Jonathan Fischer's Java implementation.</p> / Master of Science (MSc)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/11286 |
| Date | 10 1900 |
| Creators | Weng, Chia-Chun |
| Contributors | Franek, Frantisek, Antoine Deza, Emil Sekerinski, Antoine Deza, Emil Sekerinski, Computing and Software |
| Source Sets | McMaster University |
| Detected Language | English |
| Type | thesis |
Page generated in 0.0024 seconds