Блог пользователя tom

Hard string problem
Автор tom, история, 7 лет назад, По-английски

You are given two strings — text t and pattern p. You need to find index i such that t[i...i + p.size() - 1] and p have the largest "match value". Match value of two strings of equal length a and b is total number of such j that a[j] = b[j].

Can you do this faster than O(n2) (tricks with bitsets do not count)?

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

Is the alphabet small?

One can do it in O(A * N * log N) time. For a fixed letter, we need to compute dot products of the corresponding bit vectors (where 1 stands for this letter and 0 stands for the rest) for all values of i. We can do it efficiently be reversing the bit vector for t and multiplying two bit vectors as polynomials using FFT.

Once we know how to compute the answer for one letter, we just need to find the sum over all letters in the alphabet.

Here's a problem that asks to do something like this: Fuzzy Search.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Thanks, I didn't think of using FFT here.

    Is the alphabet small? — yeah, during thinking about the problem I also assumed that we have small alphabet. I wonder if there is a solution without this assumption.

    → Ответить