52 citations · 133 across the 25 of their papers we have counts for
4 papers · 1 filter
Lower bounds for text indexing with mismatches and differences
Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya
In this paper we study lower bounds for the fundamental problem of text indexing with mismatches and differences. In this problem we are given a long string of length , the "tex…
Streaming dictionary matching with mismatches
Paweł Gawrychowski, Tatiana Starikovskaya
In the -mismatch problem we are given a pattern of length and a text and must find all locations where the Hamming distance between the pattern and the text is at most .…
Fast entropy-bounded string dictionary look-up with mismatches
Paweł Gawrychowski, Gad M. Landau, Tatiana Starikovskaya
We revisit the fundamental problem of dictionary look-up with mismatches. Given a set (dictionary) of strings of length and an integer , we must preprocess it into a dat…
Upper and lower bounds for dynamic data structures on strings
Raphael Clifford, Allan Grønlund, Kasper Green Larsen +1
We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the patte…