跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.11552 · v1

Internal Queries for Maximal Closed Substrings

首次提交 2026-11-09 02:50
版本更新 2026-11-09 02:50
雷达观测 2026-11-10 13:19
arXiv ↗PDF ↗

摘要

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 O(nlog⁡n)O(n\log n) bounds on the global MCS families of a length-nn 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 O(nlog⁡n)O(n\log n)-word index that reports the cc answers in O(log⁡n+c)O(\log n+c) time and supports counting and longest queries in O(log⁡n)O(\log n) time. Our main result reduces reporting space to O(n)O(n) words, with O((c+1)log⁡1+εn)O((c+1)\log^{1+\varepsilon} n) query time and O(nlog⁡1+εn)O(n\log^{1+\varepsilon} n) construction time for any fixed ε>0\varepsilon>0. 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 3(s−1)3(s-1) MCS occurrences of any length-ss 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-ss block. A family over two letters attains ⌊(s−1)/2⌋\lfloor(s-1)/2\rfloor crossings for every s≥3s\ge3, showing that the linear order of this local density bound is optimal.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 O(nlog⁡n)O(n\log n) bounds on the global MCS families of a length-nn 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 O(nlog⁡n)O(n\log n)-word index that reports the cc answers in O(log⁡n+c)O(\log n+c) time and supports counting and longest queries in O(log⁡n)O(\log n) time. Our main result reduces reporting space to O(n)O(n) words, with O((c+1)log⁡1+εn)O((c+1)\log^{1+\varepsilon} n) query time and O(nlog⁡1+εn)O(n\log^{1+\varepsilon} n) construction time for any fixed ε>0\varepsilon>0. 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 3(s−1)3(s-1) MCS occurrences of any length-ss 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-ss block. A family over two letters attains ⌊(s−1)/2⌋\lfloor(s-1)/2\rfloor crossings for every s≥3s\ge3, showing that the linear order of this local density bound is optimal.

查看此版本解读 →查看此版本原文 ↗