Computing Maximal Repeating Subsequences in a String
Mingyang Gong, Adiesha Liyanage, Braeden Sopp, Binhai Zhu · 2026
Read Computing Maximal Repeating Subsequences in a String by Mingyang Gong, Adiesha Liyanage, Braeden Sopp, Binhai Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12200.txt.
Introduction
Mingyang Gong, Adiesha Liyanage, Braeden Sopp, and Binhai Zhu start the study of maximal repeating patterns in a single string. A maximal pattern is one that cannot be grown, though it may not be the longest. Like tasks on two or more strings were studied from 2019 by Hirota and Sakai.
The one-string case is new ground in their work. Repeating patterns help compress text and find motifs in bio data. Algorithms for the maximal case can be faster than for the maximum. The team set out the problem and its first results.
Catalog record
| CREATOR | Mingyang Gong, Adiesha Liyanage, Braeden Sopp, Binhai Zhu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-12200
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computing Maximal Repeating Subsequences in a String Mingyang Gong, Adiesha Liyanage, Braeden Sopp, Binhai Zhu Abstract In this paper we initiate the study of computing a maximal (not necessarily maximum) repeating pattern in a single input string, where the corresponding problems have been studied (e.g., a maximal common subsequence) only in two or more input strings by Hirota and Sakai starting 2019. Given an input string S S of length n n , we can compute a maximal square subsequence of S S in O ( n log n ) O(n\log n) time, greatly improving the O ( n 2 ) O(n^{2}) bound for computing the longest square subsequence of S S . For a maximal k k -repeating subsequence, our bound is O ( f ( k ) n log n ) O(f(k)n\log n) , where f ( k ) f(k) is a computable function such that f ( k ) < k ⋅ 4 k f(k)<k\cdot 4^{k} . This greatly improves the O ( n 2 k − 1 ) O(n^{2k-1}) bound for computing a longest k k -repeating subsequence of S S , for k ≥ 3 k\geq 3 . Both results hold for the constrained case, i.e., when the solution must contain a subsequence X X of S S , though with higher running times. 1 Introduction Computing (non-contiguous) patterns in two or more input strings is a classical problem which has found many applications. The textbook example is the longest common subsequence (LCS) of two strings of a total length of n , which was solved by Wagner and Fischer in O(n^{2}) time and space [ 14 ] and then in O(n^{2}) time but O(n) space by Hirschberg [ 6 ] . It has been researched and applied in various applications, sometimes with additional constraint, e.g., the LCS must also contain a pattern X , which is a subsequence appearing in both input strings A and B . If A , B and X are all of length O(n) , Tsai gave an O(n^{5}) time algorithm [ 13 ] . The bound was improved to O(n^{3}) by Chin et al. [ 3 ] and also by Chen and Chao [ 2 ] , the latter additionally considered the version where the LCS of A and B must not include X as a subsequence. A few years ago, based on the observed phenomena in applications that sometimes the longest common subsequence might not capture the truely needed or observed pattern in many applications, Sakai studied the maximal common subsequence (MCS) of two strings [ 10 , 11 ] . For two strings A and B with a total length of n , Sakai can compute an MCS of A and B in O(n\log n) time 1 1 1 The claimed time bounds in [ 10 , 11 ] are incorrect as the construction cost of the used data structure was not counted [ 5 ] . Later, given m strings with a total length of n , Hirota and Sakai presented an algorithm which can compute an MCS in O(mn\log n) time [ 4 ] . Both of these algorithms work for the case when the solution must contain a pattern (or subsequence) of A and B . In many biological applications, sometimes useful non-contiguous patterns exist in a single input string. For example, plants go through up to three whole genome duplications; hence there is a general repetition pattern (even after some subsequent local mutations) [ 16 ] . Applications like this motivate the Longest Square Subsequence (LSS) problem, i.e., a longest pattern like AA where both AA and A itself are subsequences of an input sequence S of length n , for which Kosowski gave an O(n^{2}) time algorithm in 2004 [ 7 ] . For the longest k -repeating subsequence, i.e., a longest pattern like A^{k} where both A^{k} and A are subsequence of S , there is a trivial algorithm: just enumerate k-1 cuts in S and then compute the longest common subsequence of the resulting k strings. This results in an O(n^{2k-1}) time algorithm; unfortunately, this is the best known algorithm for k\geq 3 . For k=3 , Wang and Zhu gave a parameterized O(q^{2}n^{3}) time algorithm, where q is the minimum number of letters deleted in S to have a solution [ 15 ] . However, when q=O(n) the worst-case running time of this algorithm remains to be O(n^{2}\times n^{3})=O(n^{5}) . Recently, motivated by recovering patterns from tandem duplications, Lai et al. studied the Longest Letter-duplicated Subsequence (LLDS) and related problems [ 9 ] . Here a letter-duplicated subsequence (LDS) is a subsequence of S in the form \prod_{i=1}^{k}x_{i}^{d_{i}} , where x_{i} is a letter in S and d_{i} is an integer at least 2. They showed that LLDS can be solved in O(n) time. In fact, this problem is closely related to the Maximum Run problem from computational genomics where each letter x_{i} can only appear in a run (i.e., consecutively) at most once, and d_{i}\geq 1 [ 12 , 1 ] . Very recently, Lafond et al. studied the more general problem called Longest Subsequence-duplicated Subsequence (LSDS) and related problems, where a subsequence-duplicated subsequence (SDS) is a subsequence of S in the form \prod_{i=1}^{k}X_{i}^{d_{i}} , where X_{i} is a subsequence in S and d_{i} is an integer at least 2 [ 8 ] . They showed that LSDS can be solved in O(n^{6}) time, where the fundamental subroutines are to compute the longest square and cubic sequences of (a substring of) S . In this paper, we follow the footsteps of Hirota and Sakai to initiate the research for computing various maximal repeating subsequences in a single string S of length n . We summarize our results as follows: 1. A maximal square subsequence of S can be computed in O(n\log n) time. 2. A maximal k -repeating subsequence of S can be computed in O(f(k)\cdot n\log n) time for k\geq 3 and f(k) is a computable function on k , i.e., when k=O(1) the running time is O(n\log n) . The paper is organized as follows. In Section 2 we give necessary definitions. In Section 3 we present the result to compute a maximal square subsequence of S . In Section 4 we present the result to compute a maximal k -repeating subsequence of S . In Section 5 we conclude the paper by giving some open problems. 2 Preliminaries 2.1 Basics Let \Sigma be an alphabet and S be a given sequence over the alphabet \Sigma . We let n=|S| denote the length of S and m=|\Sigma| denote the size of \Sigma , respectively. For every 1\leq i\leq|S| , we denote by S[i] the i -th character in S . A sequence X is a subsequence of S if there exist 1\leq i_{1}<i_{2}<\ldots<i_{|X|}\leq|S| such that X=S[i_{1}]S[i_{2}]\ldots S[i_{|X|}] ; in this case we also abuse the notation by writing X\subseteq S . We denote the empty string as \epsilon . Given two positive integers 1\leq i<j\leq|S| , we denote by S[i,j] the substring of S that begins with S[i] and ends at S[j] .