Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/11286
Title: | Implementing Efficient Algorithms for Computing Runs |
Authors: | Weng, Chia-Chun |
Advisor: | Franek, Frantisek Antoine Deza, Emil Sekerinski Antoine Deza, Emil Sekerinski |
Department: | Computing and Software |
Keywords: | run;repetition;periodicity;string;Theory and Algorithms;Theory and Algorithms |
Publication Date: | Oct-2011 |
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> |
URI: | http://hdl.handle.net/11375/11286 |
Identifier: | opendissertations/6266 7252 2253075 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 3.19 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.