Internal Pattern Matching (IPM) queries on a length-<InlineEquation ID="IEq1"> <EquationSource Format="TEX">$n$</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> text T, given two fragments X and Y of T such that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$|Y|<2|X|$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>Y</mi> <mo stretchy="false">|</mo> <mo><</mo> <mn>2</mn> <mo stretchy="false">|</mo> <mi>X</mi> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation>, ask to compute all exact occurrences of X within Y. IPM queries have been introduced by Kociumaka, Radoszewski, Rytter, and Waleń [SODA’15 & SICOMP’24], who showed that they can be answered in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {O}(1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time using a data structure of size <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {O}(n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and used this result to answer various queries about fragments of T. In this work, we study IPM queries on compressed and dynamic strings. Our result is an <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {O}(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-time query algorithm applicable to any balanced recompression-based run-length straight-line program (RLSLP). In particular, one can use it on top of the RLSLP of Kociumaka, Navarro, and Prezza [IEEE TIT’23], whose size <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathcal {O}\big (\delta \log \frac{n\log \sigma }{\delta \log n}\big )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">(</mo> </mrow> <mi>δ</mi> <mo>log</mo> <mfrac> <mrow> <mi>n</mi> <mo>log</mo> <mi>σ</mi> </mrow> <mrow> <mi>δ</mi> <mo>log</mo> <mi>n</mi> </mrow> </mfrac> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is optimal (among all text representations) as a function of the text length n, the alphabet size <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation>, and the substring complexity <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> </math></EquationSource> </InlineEquation>. Our procedure does not rely on any preprocessing of the underlying RLSLP, which makes it readily applicable on top of the dynamic strings data structure of Gawrychowski, Karczmarz, Kociumaka, Łącki and Sankowski [SODA’18], which supports fully persistent updates in logarithmic time with high probability.

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts

期刊论文
出版模式：

开放获取
发表日期：

2026年2月23日

查看全文

Anouk Duyster,
Tomasz Kociumaka

摘要

Internal Pattern Matching (IPM) queries on a length- $n$ $n$ text T, given two fragments X and Y of T such that $|Y|<2|X|$ $| Y | < 2 | X |$ , ask to compute all exact occurrences of X within Y. IPM queries have been introduced by Kociumaka, Radoszewski, Rytter, and Waleń [SODA’15 & SICOMP’24], who showed that they can be answered in $\mathcal {O}(1)$ $O (1)$ time using a data structure of size $\mathcal {O}(n)$ $O (n)$ and used this result to answer various queries about fragments of T. In this work, we study IPM queries on compressed and dynamic strings. Our result is an $\mathcal {O}(\log n)$ $O (log n)$ -time query algorithm applicable to any balanced recompression-based run-length straight-line program (RLSLP). In particular, one can use it on top of the RLSLP of Kociumaka, Navarro, and Prezza [IEEE TIT’23], whose size $\mathcal {O}\big (\delta \log \frac{n\log \sigma }{\delta \log n}\big )$ $O (δ log \frac{n log σ}{δ log n})$ is optimal (among all text representations) as a function of the text length n, the alphabet size $\sigma $ $σ$ , and the substring complexity $\delta $ $δ$ . Our procedure does not rely on any preprocessing of the underlying RLSLP, which makes it readily applicable on top of the dynamic strings data structure of Gawrychowski, Karczmarz, Kociumaka, Łącki and Sankowski [SODA’18], which supports fully persistent updates in logarithmic time with high probability.