BubbleDream's blog

By BubbleDream, history, 5 years ago, In English

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

How to solve this problem?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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