BubbleDream's blog

By BubbleDream, history, 8 months ago, In English,


How to solve this problem?

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

8 months 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


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