DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.58

Nearly Optimal Internal Dictionary Matching

Authors: Jingbang Chen, Jiangqi Dai, Qiuyang Mang, Qingyu Shi, and Tingqiang Xu

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We study the internal dictionary matching (IDM) problem where a dictionary 𝒟 containing d substrings of a text T over a linearly sortable alphabet is given, and each query concerns the occurrences of patterns in 𝒟 in another substring of T. We propose a novel O(n)-sized data structure named Basic Substring Structure (BASS) where n is the length of the text T. With BASS, we are able to handle all types of queries in the IDM problem in nearly optimal query and preprocessing time. Specifically, our results include: - The first algorithm that answers the CountDistinct query in Õ(1) time with Õ(n+d) preprocessing, where we need to compute the number of distinct patterns that exist in T[l,r]. Previously, the best result was Õ(m) time per query after Õ(n²/m+d) or Õ(nd/m+d) preprocessing, where m is a chosen parameter. - Faster algorithms for two other types of internal queries. We improve the runtime for (1) Occurrence counting (Count) queries to O(log n/log log n) time per query with O(n+d√{log n}) preprocessing from O(log² n/log log n) time per query with O(nlog n/log log n + d log^{3/2} n) preprocessing. (2) Distinct pattern reporting (ReportDistinct) queries to O(1+|output|) time per query from O(log n+|output|) per query. In addition, we match the optimal runtime in the remaining two types of queries, pattern existence (Exists), and occurrence reporting (Report). We also show that BASS is more generally applicable to other internal query problems.

Cite as

Jingbang Chen, Jiangqi Dai, Qiuyang Mang, Qingyu Shi, and Tingqiang Xu. Nearly Optimal Internal Dictionary Matching. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 58:1-58:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2026.58,
  author =	{Chen, Jingbang and Dai, Jiangqi and Mang, Qiuyang and Shi, Qingyu and Xu, Tingqiang},
  title =	{{Nearly Optimal Internal Dictionary Matching}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{58:1--58:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.58},
  URN =		{urn:nbn:de:0030-drops-271944},
  doi =		{10.4230/LIPIcs.ESA.2026.58},
  annote =	{Keywords: Internal dictionary matching, pattern matching, string algorithms, data structures, substring queries}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.18

Distance Queries over Dynamic Interval Graphs

Authors: Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

We design the first dynamic distance oracles for interval graphs, which are intersection graphs of a set of intervals on the real line, and for proper interval graphs, which are intersection graphs of a set of intervals in which no interval is properly contained in another. For proper interval graphs, we design a linear space data structure which supports distance queries (computing the distance between two query vertices) and vertex insertion or deletion in O(lg n) worst-case time, where n is the number of vertices currently in G. Under incremental (insertion only) or decremental (deletion only) settings, we design linear space data structures that support distance queries in O(lg n) worst-case time and vertex insertion or deletion in O(lg n) amortized time, where n is the maximum number of vertices in the graph. Under fully dynamic settings, we design a data structure that represents an interval graph G in O(n) words of space to support distance queries in O(n lg n/S(n)) worst-case time and vertex insertion or deletion in O(S(n)+lg n) worst-case time, where n is the number of vertices currently in G and S(n) is an arbitrary function that satisfies S(n) = Ω(1) and S(n) = O(n). This implies an O(n)-word solution with O(√{nlg n})-time support for both distance queries and updates. All four data structures can answer shortest path queries by reporting the vertices in the shortest path between two query vertices in O(lg n) worst-case time per vertex. We also study the hardness of supporting distance queries under updates over an intersection graph of 3D axis-aligned line segments, which generalizes our problem to 3D. Finally, we solve the problem of computing the diameter of a dynamic connected interval graph.

Cite as

Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance Queries over Dynamic Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2023.18,
  author =	{Chen, Jingbang and He, Meng and Munro, J. Ian and Peng, Richard and Wu, Kaiyu and Zhang, Daniel J.},
  title =	{{Distance Queries over Dynamic Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.18},
  URN =		{urn:nbn:de:0030-drops-193207},
  doi =		{10.4230/LIPIcs.ISAAC.2023.18},
  annote =	{Keywords: interval graph, proper interval graph, intersection graph, geometric intersection graph, distance oracle, distance query, shortest path query, dynamic graph}
}

Search Results

Documents authored by Chen, Jingbang

Nearly Optimal Internal Dictionary Matching

Abstract

Cite as

Distance Queries over Dynamic Interval Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message