Lower bounds for text indexing with mismatches and differences

DOI10.1137/1.9781611975482.70zbMath1431.68169arXiv1812.09120OpenAlexW2902292024MaRDI QIDQ5236254

Laurent Feuilloley, Tatiana Starikovskaya, Vincent Cohen-Addad

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.09120

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (3)

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Refining the \(r\)-index

This page was built for publication: Lower bounds for text indexing with mismatches and differences