**Problem statement:**http://codeforces.com/contest/356/problem/B

**Solution:**First observation which is easy to make is that it is easier to calculate where the characters match instead of mismatch and that we do not need to compute n*x and m*y. This is true:

\( (n \cdot x)[dx + i \cdot |x|] = x[(dx + i \cdot |x|) \mod |x|] \)

If i*|x| = t (mod |y|), then i*|x| - j*|y| = t, for some j. Using bezouts identity we know that t = gcd(|x|, |y|) * k, for some k. This means that all sequences make jumps of length gcd(|x|, |y|). With this information and the frequency of all characters within the second string for each repeating sequence, an efficient algorithm can be developed.

## No comments:

## Post a Comment