BubbleDream's blog

By BubbleDream, history, 3 weeks 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  

»
3 weeks 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