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 …

We propose a new linear-size data structure which provides a fast access to all palindromic
substrings of a string or a set of strings. This structure inherits some ideas from the …

Palindromic length of a string is the minimum number of palindromes whose concatenation
is equal to this string. The problem of finding the palindromic length drew some attention …

Uncertain sequences are compact representations of sets of similar strings. They highlight
common segments by collapsing them, and explicitly represent varying segments by listing …

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 …

We propose a data structure and an online algorithm to report the number of distinct
palindromes in any substring of an input string. Assume that the string S of length n arrives …

A generalised degenerate string (GD string) S^ is a sequence of n sets of strings of total size
N, where the ith set contains strings of the same length k_i but this length can vary between …

A degenerate symbol over an alphabet Σ is a non-empty subset of Σ, and a sequence of
such symbols is a degenerate string. We investigate the exact computation of maximal …

Lyndon factorization and Lempel-Ziv (LZ) factorization are both important tools for analysing
the structure and complexity of strings, but their combinatorial structure is very different. In …

We revisit the classic algorithmic problem of computing a longest palidromic substring. This
problem is solvable by a celebrated 𝒪 (n)-time algorithm [Manacher, J. ACM 1975], where n …