405224: GYM101848 H Loop String

There are two strings s, t, with length infinity. Their periods are n and m, respectively.

Period of a string, has the following definition: if s has a period of n, then s[1..n] = s[n + 1..2n] = s[dn + 1..(d + 1)n] for all d ≥ 0, in which s[i..j] is a substring of s starting from the i-th character and ends with the j-th character.

Now we want to know how many i (1 ≤ i ≤ k) satisfies s_i = t_i. In other words, in how many positions s[1..k] and t[1..k] have the same character?

The first line contains three space-separated integers n, m, k (1 ≤ n, m ≤ 125 512, 1 ≤ k ≤ 10¹⁸).

The second line contains a string with length n, which is one period of s.

The third line contains a string with length m, denoting t.

For some mysterious reasons, s and t both consist of only four upper-case letters: A, G, C and T.

Output the answer.

5 4 9
AGCAG
AGCC

5

5 4 9
AAAAA
AAAA

9