← 研踪 PaperTrailarXiv:2611.11552 · v1
Internal Queries for Maximal Closed Substrings
首次提交 2026-11-09 02:50
版本更新 2026-11-09 02:50
雷达观测 2026-11-10 13:19
摘要
Searching for repetitions inside a selected part of a text raises a subtle boundary problem: removing neighbouring characters can create new maximal answers. We study this effect for maximal closed substrings (MCSs). A string is closed if it is a single letter or has a nonempty proper prefix occurring exactly twice, as its prefix and suffix; a closed occurrence is maximal if neither available one-character extension is closed. Previous work established bounds on the global MCS families of a length- text and developed enumeration algorithms. Internal queries instead ask for the MCSs of a chosen substring, with maximality evaluated inside that substring. Separating boundary occurrences from interior ones gives an -word index that reports the answers in time and supports counting and longest queries in time. Our main result reduces reporting space to words, with query time and construction time for any fixed . Thus, after preprocessing, reporting requires no additive scan of the queried substring, which is particularly useful for long queries with few answers. Independently, we prove that at most MCS occurrences of any length- substring cross a fixed gap between consecutive characters, with maximality evaluated inside that substring. The same bound holds for global MCSs contained in a length- block. A family over two letters attains crossings for every , showing that the linear order of this local density bound is optimal.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-09 02:50 · 最新观测版本
Internal Queries for Maximal Closed Substrings
Searching for repetitions inside a selected part of a text raises a subtle boundary problem: removing neighbouring characters can create new maximal answers. We study this effect for maximal closed substrings (MCSs). A string is closed if it is a single letter or has a nonempty proper prefix occurring exactly twice, as its prefix and suffix; a closed occurrence is maximal if neither available one-character extension is closed. Previous work established bounds on the global MCS families of a length- text and developed enumeration algorithms. Internal queries instead ask for the MCSs of a chosen substring, with maximality evaluated inside that substring. Separating boundary occurrences from interior ones gives an -word index that reports the answers in time and supports counting and longest queries in time. Our main result reduces reporting space to words, with query time and construction time for any fixed . Thus, after preprocessing, reporting requires no additive scan of the queried substring, which is particularly useful for long queries with few answers. Independently, we prove that at most MCS occurrences of any length- substring cross a fixed gap between consecutive characters, with maximality evaluated inside that substring. The same bound holds for global MCSs contained in a length- block. A family over two letters attains crossings for every , showing that the linear order of this local density bound is optimal.
查看此版本解读 →查看此版本原文 ↗