CCCHK '15 S2 - Matching Problem - Olympiads Online Judge

CCCHK '15 S2 - Matching Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

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

$A$ ~A~ and $B$ ~B~ have equal string length;
$A$ ~A~ is generated by concatenating $S$ ~S~ for $N$ ~N~ times;
$B$ ~B~ is generated by concatenating $T$ ~T~ for $M$ ~M~ times.

It is regarded as a match if the $i$ ~i~-th character in $A$ ~A~ is the same as the $i$ ~i~-th character in $B$ ~B~. Given $N,M,S,T$ ~N,M,S,T~, please write a program to return the number of matches among $A$ ~A~ and $B$ ~B~.

Input Specification

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

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

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

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