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 $n$, the "tex…