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

How to solve this problem?

Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3496 |

3 | apiadu | 3438 |

4 | TLE | 3356 |

5 | LHiC | 3339 |

6 | mnbvmar | 3281 |

7 | 300iq | 3267 |

8 | Radewoosh | 3242 |

9 | yosupo | 3233 |

10 | 1919810 | 3203 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 168 |

4 | vovuh | 168 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 154 |

10 | McDic | 152 |

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

How to solve this problem?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2020 06:42:49 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 polynomialx^{0}+x^{3}+x^{4}+x^{5}And for character

`A`

, and r you will constructx^{0}+x^{ - 2}+x^{ - 3}.Now when you multiply them, the coefficient of

x^{k}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`