## CCCHK '15 S2 - Matching Problem

View as PDF

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

Problem types

Given two positive integers and , and two strings and of lowercase letters, we generate two strings and so that they have the following characteristics:

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

#### Input specification:

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

The second and third line contain string and , respectively.

It is guaranteed that and have equal string length.

• In of the test cases, the length of .
• In of the test cases, the length of and the length of .
• In of the test cases, ,, the length of , the length of .

#### Output specification:

Print the number of matches among and .

#### 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, ababaababaababa, abaabaabaabaaba. Hence, when .