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

Автор BubbleDream, история, 5 лет назад, По-английски

https://www.spoj.com/problems/ADAMATCH/

How to solve this problem?

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This problem can be solved in a similar way as MAXMATCH.

You can first find maximum matching of the two strings by keeping s fixed and varying r. To achieve that you can construct polynomial for each of the different character, by raising x to the powers of indexes in s and to negative of powers of index in r. For example consider

s = ATCAAA r = ACAA

Now for character A, and s you will construct polynomial x0 + x3 + x4 + x5

And for character A, and r you will construct x0 + x - 2 + x - 3.

Now when you multiply them, the coefficient of xk will represent number of matching indexes for A in kth shift.

You can just sum that over all four characters and answer will res.size() - maximum_matching

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    But, how we will multiply them? FFT multiplies polynomials with non-zero powers of x.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain why r contains the negative of powers of index?