### BubbleDream's blog

By BubbleDream, history, 8 months ago, ,

 » 8 months ago, # |   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 = ACAANow for character A, and s you will construct polynomial x0 + x3 + x4 + x5And 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