Longest (Sub-)Periodic Subsequence

A natural extension of the analysis of regularities such as squares or palindromes perceived as substrings of a given text is the study of the same type of regularities when considering subsequences. In this line of research, given a text of length $n$, Kosowski [17] proposed an algorithm running in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ time using $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ words of space to find the longest subsequence that is a square. Inoue et al. [13] generalized this setting to consider the longest such subsequence common of two texts $T$ and $S$ of length $n$, and gave an algorithm computing this sequence in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{6})$ time using $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{4})$ space, also providing improvements in case that the number of matching characters pairs $T[i]=S[j]$ is rather small. Recently, Inoue et al. [14] provided similar improvements for the longest square subsequence of a single string. Here, we consider the problem for a single text, but allow the subsequence to have different exponents. In detail, we want to find the longest subsequence that is (sub-)periodic.

A non-exhaustive list of related problems are finding the longest palindromic subsequence [5, 12], absent subsequences [16], longest increasing and decreasing subsequences [19, 7], maximal common subsequences [18, 6], the longest run subsequence [20], the longest Lyndon subsequence [2], longest rollercoasters [9, 3, 8], and computing subsequence automaton [4, 1]. Our techniques rely on finding longest common subsequences, which is conceived as a well-studied problem (see [10, 11, 15] and the references therein).

Let $\mathbb{N}$ denote all natural numbers $1,2,\ldots$, and $\mathbb{Q}^{+}$ the set of all rational numbers greater than or equal to 1. We distinguish integer intervals $1,\ldots,n=[1..n]$ and intervals of rational numbers $[1/2,3/4]$.

Let $\Sigma$ denote a totally ordered set of symbols called the alphabet. An element of $\Sigma^{*}$ is called a string. Given a string $S\in\Sigma^{*}$, we denote its length with $|S|$ and its $i$-th symbol with $S[i]$ for $i\in[1..|S|]$. Further, we write $S[i..j]=S[i]\cdots S[j]$. A factorization $T=F_{1}\cdots F_{z}$ is a partitioning of $T$ into substrings $F_{1},\ldots,F_{z}$. A subsequence of a string $S$ with length $\ell$ is a string $S[i_{1}]\cdots S[i_{\ell}]$ with $i_{1}<\ldots<i_{\ell}$.

Given a string $S$, we can write $S$ in the form $S=U^{x}U^{\prime}$ with $U^{\prime}$ being either empty or a proper prefix of $U$. Then $|U|$ is called a period of $S$, and $x+|U^{\prime}|/|U|\in\mathbb{Q}^{+}$ is called its exponent with respect to the period $|U|$. For the largest possible such exponent $x$, $S$ is called periodic if $x\geq 2$, or sub-periodic if $x\in(1,2)$. For instance, the unary string $T=\texttt{a}\cdots\texttt{a}$ has the minimum period $1$ with exponent $|T|$, or more generally, period $p\in[1..|T|]$ with exponent $|T|/p$.

Further, for two strings $Y$ and $Z$, let ${\textrm{LCS}}_{Y,Z}({y,z})$ denote the longest common subsequence of $Y[1..y]$ and $Z[1..z]$. We omit the strings in subscript if they are clear from the context. Also, we allow us to write LCS for an arbitrary number of strings; the number of strings is reflected by the arguments given to LCS. It is known that we can answer the longest common subsequence ${\textrm{LCS}}_{X_{1},\ldots,X_{k}}({x_{1},\ldots,x_{k}})$ of $k$ strings $X_{1}[1..x_{1}],\ldots,X_{k}[1..x_{k}]$ in constant time by building a table of size $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{k})$ and filling its entries in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(kn^{k})$ time via dynamic programming.

We start with the search for the longest subsequence that is periodic or subperiodic, meaning that one of its exponents is in $\mathbb{Q}^{+}\setminus\mathbb{N}=(1,2)\cup(2,3)\cup(3,4)\cdots$. The idea is to compute every possible factorization of $T=YZ$ into two factors, and try to (a) prolong each square $UU$ to $UcU$ for $Uc$ being a subsequence in $Y$, or (b) extend $UU^{\prime}$ to $UcU^{\prime}$ with $U^{\prime}$ being a proper prefix of $U$ found in $Z$ and $Uc$ a subsequence found in $Y$. For a fixed partition $T=YZ$, we define

for $y\in[1..|Y|]$ and $z\in[1..|Z|]$ to be the longest subsequence of $T$ having an exponent in $\mathbb{Q}^{+}\setminus\mathbb{N}$ of the form $UU^{\prime}$ with $U^{\prime}$ being a non-empty common subsequence of $Y[1..y]$ and $Z[1..z]$ and $U$ a subsequence of $Y[1..y]$, where $D_{2}[\cdot,0]:=D_{2}[0,\cdot]:=0$. Note that we can add $D_{2}[y-1,z-1]+1\text{~{}if~{}}D_{2}[y-1,z-1]>0$ as another selectable value for the maximum determining $D_{2}[y,z]$, but this does not change the maximum, since the value of $D_{2}[y-1,z-1]+1$ is used as an option for the maximum determining $D_{2}[y,z-1]$, which is already an option for $D_{2}[y,z]$. $D_{2}$ has the following property:

In the following we want to omit subsequences having exponents only in $[1,2)$.

We now extend our ideas of the previous section to omit the sub-periodic subsequences, such that our algorithm always reports a subsequence with an exponent of at least $2$. Our main idea is to generalize the factorization of $T$ from $2$ to $k$ factors. Computing the LCS of these $k$ factors, we obtain all longest periodic subsequences having an exponent of length $k\ell$ with $\ell\in\mathbb{N}$. For $k=2$, we can find all square subsequences, i.e., the longest common subsequence with an exponent of $2x$ for $x\in\mathbb{N}$, similar to [17]. Like in Sect. 3, we can support exponent values $\ell\in\mathbb{Q}^{+}$ by stopping matching characters in the last factor. In general, the number of factors $k=3$ is a good value if the exponent is not in $(3,4)$. With an exponent $x\in(3,4)$, each factor starts capturing at the root of the repetition, i.e., if we match a subsequence $S=U^{\left\lfloor x\right\rfloor}U^{\prime}$, then we start capturing $U$ in all factors simultaneously. However, the last factor has to capture $|UU^{\prime}|$ characters if $x\in(3,4)$. Hence, we need to split this last factor such that we have four factors, i.e., we need $k=4$ for $x\in(3,4)$.

However, $k=3$ suffices for $x\in(2,3]\cup[4,\infty)$. To see that, we let the first $k-1$ factor capture the subsequence $U^{\left\lfloor x/k-1\right\rfloor}$. The last factor captures $U^{y}$ with $y=x-\left\lfloor x/(k-1)\right\rfloor(k-1)$, which works if $y\leq\left\lfloor x/(k-1)\right\rfloor$, i.e., $x\leq 3\left\lfloor x/2\right\rfloor$, which holds for $x\geq 4$. For $x\in(2,3]$, each of the first factors captures $U$, while the last factor captures $U^{y}$ with $y\leq 1$.

We are unaware of polynomial-time algorithms computing several other types of regularities when considering subsequences. For instance, we are not aware of an algorithm computing the longest sub-periodic subsequence. For that, we would need an efficient algorithm computing the longest (common) subsequence without a border. Then we could use the algorithm of Sect. 3 and compute this subsequence without a border instead of the (plain) LCS. Other problems are finding the longest (common) subsequence that is primitive (exponent in $(1,\infty)\setminus\mathbb{N}$), or the longest (common) subsequence that is non-primitive (exponent in $\mathbb{N}\setminus\{1\}$).