pipette
ENEnglish

Internal Queries for Maximal Closed Substrings

Simone Faro, Francesco Pio Marino, Arianna Pavone

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.