Abstract
dc:description.abstract<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>
Degree
thesis:*- Department dc:contributor.department
- Computing and Software
- Year dc:date.issued
- 2011
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Weng, Chia-Chun
- Advisors dc:contributor.advisor
-
- Franek, Frantisek
- Antoine Deza, Emil Sekerinski
Subjects
dc:subject × 5Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/20105
- Dc Identifier Other
-
opendissertations/6266
7252
2253075