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 \le 10^5.
  • In 40\% of the test cases, the length of S \le 10 and the length of T \le 10.
  • In 100\% of the test cases, N,M \le 10^9, the length of S \le 10^6, the length of T \le 10^6.

Output Specification

Print the number of matches among A and B.

Sample Input 1

3 5

Sample Output 1


Explanation for Sample 1

A = ababaababaababa, B = abaabaabaabaaba. Hence, A_i = B_i when i = 1,2,3,6,10,13,14,15.

Sample Input 2

30 20

Sample Output 2



There are no comments at the moment.