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

Abstract Internal Pattern Matching (IPM) queries on a length- $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> text T , given two fragments X and Y of T such that $$|Y|&lt;2|X|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>Y</mml:mi> <mml:mo>|</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mn>2</mml:mn> <mml:mo>|</mml:mo> <mml:mi>X</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:math> , ask to compute all exact occurrences of X within Y . IPM queries have been introduced by Kociumaka, Radoszewski, Rytter, and Waleń [SODA’15 &amp; SICOMP’24], who showed that they can be answered in $$\mathcal {O}(1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time using a data structure of size $$\mathcal {O}(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -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 )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>log</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:mi>σ</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:mfrac> <mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> is optimal (among all text representations) as a function of the text length n , the alphabet size $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> , and the substring complexity $$\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> . 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.