CCCHK '15 S2 - Matching Problem

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Given two positive integers N and M, and two strings S and T of lowercase letters, we generate two strings A and B so that they have the following characteristics:

  • A and B have equal string length;
  • A is generated by concatenating S for N times;
  • B is generated by concatenating T for M times. It is regarded as a match if the i-th character in A is the same as the i-th character in B. Given N,M,S,T,please write a program to return the number of matches among A and B.

Input specification:

The first line of the input contains 2 integers, representing N and M, separated by a space.

The second and third line contain string S and T, respectively.

It is guaranteed that A and B have equal string length.

  • In 20\% of the test cases, the length of A \leq 10^5.
  • In 40\% of the test cases, the length of S \leq 10 and the length of T \leq 10.
  • In 100\% of the test cases, N,M \leq 10^9, the length of S\leq 10^6, the length of T\leq 10^6.

Output specification:

Print the number of matches among A and B.

Sample Input 1

3 5
ababa
aba

Sample Output 1

8

Sample Input 2

30 20
abbb
bbaabb

Sample Output 2

70

Explanation: In the first sample, A = ababaababaababa, B = abaabaabaabaaba. Hence, A_i = B_i when i = 1,2,3,6,10,13,14,15.


Comments

There are no comments at the moment.