2026-07-23T08:46:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24501 2025-12-16T14:00:02Z ddc:004 open_access

Better Indexing for Rectangular Pattern Matching Gawrychowski, Paweł Górkiewicz, Adam 2D strings pattern matching string indexing We revisit the complexity of building, given a two-dimensional string of size n, an indexing structure that allows locating all k occurrences of a two-dimensional pattern of size m. While a structure of size 𝒪(n) with query time 𝒪(m+k) is known for this problem under the additional assumption that the pattern is a square [Giancarlo, SICOMP 1995], a popular belief was that for rectangular patterns one cannot achieve such (or even similar) bounds, due to a lower bound for a certain natural class of approaches [Giancarlo, WADS 1993]. We show that, in fact, it is possible to construct a very simple structure of size 𝒪(nlog n) that supports such queries for any rectangular pattern in 𝒪(m+klog^{ε}n) time, for any ε > 0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paweł Gawrychowski and Adam Górkiewicz 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.33 urn:nbn:de:0030-drops-245011 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.33 eng https://creativecommons.org/licenses/by/4.0/legalcode