Given two strings S and T, each of length at most n, the longest common substring (LCS)
problem is to find a longest substring common to S and T. This is a classical problem in …

A string UU for a non-empty string U is called a square. Squares have been well-studied
both from a combinatorial and an algorithmic perspective. In this paper, we are the first to …

Let T 1 and T 2 be two rooted trees with an equal number of leaves. The leaves are labeled,
and the labeling of the leaves in T 2 is a permutation of those in T 1. Nodes are associated …

In the longest common substring (LCS) problem, we are given two strings $ S $ and $ T $,
each of length at most $ n $, and we are asked to find a longest string occurring as a …

The Suffix Array $ SA_S [1\ldots n] $ of an $ n $-length string $ S $ is a lexicographically
sorted array of the suffixes of $ S $. The suffix array is one of the most well known and widely …

We consider the problem of finding, given two documents of total length $ n $, a longest
string occurring as a substring of both documents. This problem, known as the Longest …

Palindromes are important objects in strings which have been extensively studied from
combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of …

This thesis is devoted to designing and analyzing efficient text indexing data structures and
associated algorithms for processing text data. The general problem is to preprocess a given …