• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Minimal Discriminating Words Problem Revisited

P. 129-140.
Kucherov G., Nekrich Y., Gawrychowski P., Starikovskaya T.

We revisit two variants of the problem of computing minimal discriminating words studied in [5]. Given a pattern P and a threshold d, we want to report (i) all shortest extensions of P which occur in less than d documents, and (ii) all shortest extensions of P which occur only in d selected documents. For the rst problem, we give an optimal solution with constant time per output word. For the second problem, we propose an algorithm with running time O(jPj + d  (1 + output)) improving the solution of [5].

In book

Vol. 8214: Proceedings of the 20th Symposium on String Processing and Information Retrieval. Berlin: Springer, 2013.