{"ID":5551815,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T08:33:09.063375117Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00612","arxiv_id":"2607.00612","title":"Online computation of maximal closed substrings","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.","short_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 repeti...","url_abs":"https://arxiv.org/abs/2607.00612","url_pdf":"https://arxiv.org/pdf/2607.00612v1","authors":"[\"Hiroki Shibata\",\"Haruki Umezaki\",\"Takuya Mieno\",\"Yuto Nakashima\",\"Shunsuke Inenaga\"]","published":"2026-07-01T08:35:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}