Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 7 of 7 for “"Crochemore"”.
-
Subsequences and Supersequences of Strings
… in recent years. Very recently, two books [M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, 1995] and [G. Stephen, String Searching Algorithms, World Scientific, 1994] have been published on the subject and at least two others are known to be in preparation. Problems on …
-
Completing the New Periodicity Lemma
<p>The “Three Squares Lemma” (Crochemore and Rytter 1995) famously explored the consequences of supposing that three squares occur at the same position in a string. Essentially, it showed that this phenomenon could not occur unless the longest of the three squares was at least the sum of the …
-
STRUCTURAL FACTORIZATION OF SQUARES IN STRINGS
… a stronger version of the Three Squares Lemma by Crochemore and Rytter. This part of the thesis was published by Bai, Deza, and Franek.
-
Minimal Presentations of Sofic Shifts and Properties of Periodic-Finite-Type Shifts
… finite-state encoder. We follow an algorithm by Crochemore, Mignosi and Restivo which constructs a deterministic presentation of an SFT and we see how to derive a Shannon cover from the presentation under their algorithm. Furthermore, as a method to determine whether a given deterministic …
-
COMPUTING REPETITIONS IN STRINGS: CURRENT ALGORITHMS & THE COMBINATORICS OF FUTURE ONES.
… execute in ϴ(<em>n</em>log<em>n</em>) time (Crochemore, 1981; Apostolico and Preparata, 1983; Main and Lorentz, 1984) and employ computationally heavy preprocessing. An ϴ(<em>n</em>) time algorithm introduced in 2000 (Kolpakov and Kucherov, 2000) prevailed over its slower predecessors by …
-
Performance comparisons of various runs algorithms
… who implemented a space efficient version of Crochemore’s repetition algorithm [6], and then extended it to compute runs [4, 5]. The three programs tested are:</p> <p>1. crochB – a direct C++ implementation of the extension of Crochemore’s algorithm for runs by Franek, Jiang, and Weng without …
-
Practical algorithms for biological sequence analysis: methods and applications
… of the MaxShiftM bitparallel algorithm (Crochemore et al., 2010) for performing Fixed-Length Approximate String Matching (FLASM) under the Hamming distance model. We also describe how we can apply Myers’ bit-parallel approximate pattern matching algorithm (Myers, 1999) for solving the …