On Longest Common Property Preserved Substring Queries

Abstract

We revisit the problem of longest common property preserving substring queries introduced by~Ayad et al. (SPIRE 2018, arXiv 2018). We consider a generalized and unified on-line setting, where we are given a set $X$ of $k$ strings of total length $n$ that can be pre-processed so that, given a query string $y$ and a positive integer $k^{\prime }\le k$, we can determine the longest substring of $y$ that satisfies some specific property and is common to at least $k^{\prime }$ strings in $X$. Ayad et al. considered the longest square-free substring in an on-line setting and the longest periodic and palindromic substring in an off-line setting. In this paper, we give efficient solutions in the on-line setting for finding the longest common square, periodic, palindromic, and Lyndon substrings. More precisely, we show that $X$ can be pre-processed in $O(n)$ time resulting in a data structure of $O(n)$ size that answers queries in $O(|y|\log \sigma )$ time and $O(1)$ working space, where $\sigma$ is the size of the alphabet, and the common substring must be a square, a periodic substring, a palindrome, or a Lyndon word.

minor change from version submitted to SPIRE 2019