Back to search

McMaster University

Implementing Efficient Algorithms for Computing Runs

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 × 5

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/6266
7252
2253075

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Weng, Chia-Chun. Implementing Efficient Algorithms for Computing Runs. 2011. http://hdl.handle.net/11375/11286