Exploring regular structures in strings

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.