Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/11286
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Franek, Frantisek | en_US |
dc.contributor.advisor | Antoine Deza, Emil Sekerinski | en_US |
dc.contributor.advisor | Antoine Deza, Emil Sekerinski | en_US |
dc.contributor.author | Weng, Chia-Chun | en_US |
dc.date.accessioned | 2014-06-18T16:54:09Z | - |
dc.date.available | 2014-06-18T16:54:09Z | - |
dc.date.created | 2011-09-23 | en_US |
dc.date.issued | 2011-10 | en_US |
dc.identifier.other | opendissertations/6266 | en_US |
dc.identifier.other | 7252 | en_US |
dc.identifier.other | 2253075 | en_US |
dc.identifier.uri | http://hdl.handle.net/11375/11286 | - |
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> | en_US |
dc.subject | run | en_US |
dc.subject | repetition | en_US |
dc.subject | periodicity | en_US |
dc.subject | string | en_US |
dc.subject | Theory and Algorithms | en_US |
dc.subject | Theory and Algorithms | en_US |
dc.title | Implementing Efficient Algorithms for Computing Runs | en_US |
dc.type | thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degree | Master of Science (MSc) | en_US |
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.