Exploring regular structures in strings
Loading...
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis is dedicated to string processing algorithms and to combinatorics on words. With respect to the former, we devise Lempel-Ziv (LZ) factorization and sparse suffix sorting algorithms. With respect to the latter, we search for all distinct squares, all maximal α-gapped repeats, and all maximal α-gapped palindromes. The topics of the presented approaches are related: for instance, our results for the LZ factorization have applications for finding all distinct squares, whereas our sparse suffix sorting algorithm profits from finding gapped repeats. The results can contribute to tools for data compression, for text indexing, and for the analysis of biological sequences.
Description
Table of contents
Keywords
Lempel-Ziv, Sparse Suffix Sorting, Combinatorics on words