Online computation of maximal closed substrings
2026-07-01 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a way to find special repeated parts of a string called maximal closed substrings (MCS) as new characters are added one by one. They create a new data structure called the link-cut suffix tree (LCST) that helps track these parts efficiently by keeping information about the latest positions of substrings. Their method works in a total time that grows like n log n with the length of the string, which is optimal for this problem. They also show that their LCST can be used for similar tasks like finding LZ77 factorizations and recent matches online.
maximal closed substringsborder of a stringsuffix treelink-cut treeonline algorithmLZ77 factorizationstring processingmaximal repetitionsdata structure
Authors
Hiroki Shibata, Haruki Umezaki, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga
Abstract
A non-empty string is closed if its length is one or its longest border appears exactly twice in the string. An occurrence of a closed substring is a maximal closed substring (MCS) if it cannot be extended to the left or to the right while preserving closedness. MCSs can be regarded as a general class of maximal repetitive structures including runs. In this paper, we study the computation of MCSs of a string given in an online manner, where one character is appended to the string at a time. Our algorithm detects newly formed MCSs after each append operation by using the rightmost previous occurrences of suffixes. To support this efficiently, we introduce the link-cut suffix tree (LCST), a novel data structure combining an online suffix tree with a link-cut tree. The LCST maintains rightmost occurrence information for substrings represented in the suffix tree in $O(n \log n)$ total time and $O(n)$ space, where $n$ is the length of the input string. Using the LCST, we obtain an $O(n \log n)$-time online algorithm for computing all MCSs, which is worst-case optimal. As further direct applications of the LCST, we obtain online algorithms for rightmost LZ77 factorizations and most recent match queries.