Problem:


Score : 300 points

Problem Statement

You are given a string S of length N and another string T of length M.
These strings consist of lowercase English letters.

A string X is called a good string when the following conditions are all met:

Let L be the length of X. L is divisible by both N and M.

Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.

Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.

Determine if there exists a good string. If it exists, find the length of the shortest such string.

Constraints

1 \leq N,M \leq 10^5

S and T consist of lowercase English letters.

|S|=N

|T|=M

Input

Input is given from Standard Input in the following format:

N M
S
T

Output

If a good string does not exist, print -1; if it exists, print the length of the shortest such string.

Sample Input 1

3 2
acp
ae

Sample Output 1

6

For example, the string accept is a good string.
There is no good string shorter than this, so the answer is 6.

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Runtime Error

Solution code:
import math

N, M = map(int, input().split())
S = input()
T = input()
gcd = math.gcd(N, M)

if gcd == 1:
    print(N*M)
else:
    sl = [i for i in range(0, N, N//gcd)]
    tl = [i for i in range(0, M, M//gcd)]
    for i in range(len(sl)):
        if S[sl[i]] != T[tl[i]]:
            print(-1)
            break
    else:
        print(N*M//gcd)

Submission status: Runtime Error

Solution code:
import math

a = list(map(int,input().split()))
n = a[0]
m = a[1]
s = input()
t = input()
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
l = lcm(n,m)
lists = []
listt = []
for i in range(n):
    lists.append(1+i*(l//n))
for i in range(m):
    listt.append(1+i*(l//m))
#print(lists)
#print(listt)
aa = 0

flag = True
for i in lists:
    bb = 0
    for j in listt:
        if i == j:
            if s[aa] != t[bb]:
                flag = False
        bb += 1
    aa+=1
if flag:
    print(l)
else:
    print("-1")

Submission status: Runtime Error

Solution code:
from math import gcd
N,M = map(int,input().split())
S = input()
T = input()

flag = True
for n in range(N):
    if M*n%N==0:
        m = M*n//N
        flag = S[n]==T[m]
    if not flag:
        break
if not flag:
    print(-1)
else:
    print(N*M//gcd(N,M))

Submission status: Runtime Error

Solution code:
import math


N, M = map(int, input().split())
S = input()
T = input()

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
    
L = int(M*N/gcd(N, M))
X = 'A'*int(L)

for i, s in enumerate(S):
    j = int(L/N*i)
    if X[j] == 'A':
        X = X[:j]+s+X[j+1:]
    elif X[j] == s:
        continue
    else:
        print(-1)
        exit(0)

        
for i, t in enumerate(T):
    j = int(L/M*i)
    if X[j] == 'A':
        X = X[:j]+t+X[j+1:]        
    elif X[j] == t:
        continue
    else:
        print(-1)
        exit(0)

print(L)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tuple>
#include <queue>
#include <bitset>
#include <unordered_map>
#include <tuple>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sys/time.h>

using namespace std;

long long lcm(long long a, long long b) {
  long long x = a * b;
  if (a < b) {
    long long t = a;
    a = b;
    b = t;
  }

  long long r = a % b;
  while (r!=0) {
    a = b;
    b = r;
    r = a % b;
  }
  return x/b;
}

void solve(long long N, long long M, string S, string T){
  long long ret = lcm(N, M);
  vector<char> a(ret, '.');
  for (int i = 0; i < ret; i++) {
    if (i%(ret/N) == 0) {
      a[i] = S[i/(ret/N)];
    }
    if ((i%(ret/M) == 0) && a[i] != '.') {
      if (a[i] != T[i/(ret/M)]) {
        std::cout << -1 << std::endl;
        return;
      }
    }
  }
  std::cout << ret << std::endl;
  return;
}

int main(){
  string T;
  string S;
  long long N;
  long long M;
  scanf("%lld",&N);
  scanf("%lld",&M);
  cin >> S;
  cin >> T;
  solve(N, M, S, T);
  return 0;
}

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import collections
import itertools
a = list(map(int,input().split()))
n = a[0]
m = a[1]
s = input()
t = input()
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
l = lcm(n,m)
lists = []
listt = []
for i in range(n):
    lists.append(1+i*(l//n))
for i in range(m):
    listt.append(1+i*(l//m))
#print(lists)
#print(listt)
aa = 0

flag = True
for i in lists:
    bb = 0
    for j in listt:
        if i == j:
            if s[aa] != t[bb]:
                flag = False
        bb += 1
    aa+=1
if flag:
    print(l)
else:
    print("-1")

Submission status: Runtime Error

Solution code:

from fractions import gcd

def solve():
    N, M = map(int, input().split())
    S = list(input())
    T = list(input())

    k = N * M // gcd(N, M)

    S_new = ''.join([c + ' '*(k//N-1) for c in S])
    T_new = ''.join([c + ' '*(k//M-1) for c in T])

    for i in range(N):
        idx = i*(k//N)
        if S_new[idx] != ' ' and T_new[idx] != ' ' and S_new[idx] != T_new[idx]:
            print(-1)
            return
    for i in range(M):
        idx = i*(k//M)
        if S_new[idx] != ' ' and T_new[idx] != ' ' and S_new[idx] != T_new[idx]:
            print(-1)
            return
    
    print(k)

solve()

Submission status: Runtime Error

Solution code:
from math import gcd

nm = input().split()
n = int(nm[0])
m = int(nm[1])
s = input()
t = input()
g = gcd(n,m)

ans = int(n*m / g)
for i in range(g):
    if s[(n//g)*i] != t[(m//g)*i]:
        ans = -1
            
print(ans)

Submission status: Runtime Error

Solution code:
[n,m]=[int(i) for i in input().split()]
s=input()
t=input()

a = ""
b = ""
c = 1

import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

l = lcm(m, n)

for i in range(n):
    a = a + s[i] + "A" * int((l / n)-1)

for i in range(m):
    b = b + t[i] + "A" * int((l / m)-1)



for i in range(len(a)):
    if (a[i] == b[i]) or a[i] == "A" or b[i] == "A":
        c = c
    else:
        c = 0

if c == 0:
    print(-1)
else:
    print(l)

Submission status: Runtime Error

Solution code:
from sys import stdin
il = lambda func=int: list(map(func, stdin.readline().rstrip().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]
def gcd(a, b):
    if a < b: return gcd(b, a)
    if b == 0: return a
    return gcd(b, a%b)
def lcm(a, b):
    return a * b // gcd(a, b)

n, m = il()
s = input()
t = input()
ans = lcm(n, m)
hoge = "0" * ans
for i in range(n):
    nn = ans//n
    if hoge[i*nn] != "0" and hoge[i*nn] != s[i]:
        print(-1)
        exit()
    hoge = hoge[:i*nn] + s[i] + hoge[i*nn+1:]
for i in range(m):
    mm = ans//m
    if hoge[i*mm] != "0" and hoge[i*mm] != t[i]:
        print(-1)
        exit()
    hoge = hoge[:i*mm] + t[i] + hoge[i*mm+1:]
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a,b):
  if a%b==0:return b
  return gcd(b,a%b)

f=lambda x,y:x*y//gcd(x,y)
n,m=map(int,input().split())
s,t=input(),input()
lcm=f(n,m)
a,b=lcm//n,lcm//m
l=[None]*lcm

for i in range(n):
  l[i*a]=s[i]
for i in range(m):
  if l[i*b] and l[i*b]!=t[i]:
    print(-1)
    break
  l[i*b]=t[i]
else:
  print(lcm)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n,m = list(map(int, input().split()))
s = input()
t = input()

s1 = ''
for ss in s:
    s1 += ss
    s1 += 'A'*(m-1)

t1 = ''
for tt in t:
    t1 += tt
    t1 += 'A'*(n-1)

ok = 1
for k in range(len(s1)):
    if s1[k] != 'A' and t1[k] != 'A':
        if s1[k] != t1[k]:
            ok = -1
        if ok == -1:
            break
if ok == 1:
    print(int(m * n / gcd(m,n)))
else:
    print('-1')

Submission status: Runtime Error

Solution code:
import math

N, M = list(map(int, input().split()))
S = input()
T = input()
gcd = math.gcd(N, M)
lcm = N*M//gcd
if N%M==0 or M%N==0:
    exist = True
    if N>M:
        for i in range(M):
            if S[N//M*i]!=T[i]:
                exist = False
                break
    else:
        for i in range(N):
            if T[M//N*i]!=S[i]:
                exist = False
                break
    if exist:
        print(max(N, M))
    else:
        print(-1)
else:
    print(lcm)

Submission status: Runtime Error

Solution code:
import math

n, m = [int(i) for i in input().split()]
s = input()
t = input()

ans = n * m // math.gcd(n, m)

for scnt in range(n):
    if scnt * m % n == 0:
        tcnt = scnt * m // n
        if s[scnt] != t[tcnt]:
            ans = -1
            break

print(ans)

Submission status: Runtime Error

Solution code:
import math

def lcm(x, y):
	return (x * y) // math.gcd(x, y)

n, m = map(int, input().split())
s = input()
t = input()

lcm = lcm(n, m)

str1 = ""
for i in range(lcm):
	str1 += "-"

for i in range(n):
	index = i * lcm // n + 1
	str1 = str1[:index] + s[i] + str1[index+1:]

flg = 0
for i in range(m):
	index = i * lcm // m + 1
	if str1[index:index+1] != "-" and str1[index:index+1] != t[i]:
		print(-1)
		flg = 1
		break

if flg == 0:
	print(lcm)

Submission status: Runtime Error

Solution code:
from math import gcd

n, m = map(int, input().split())
s = input()
t = input()

if n % m != 0 and m % n != 0:
	print(n // gcd(n, m) * m)
elif n >= m:
	ok = True
	for i in range(m):
		if s[(n // m) * i] != t[i]:
			ok = False
			break
	if ok:
		print(n)
	else:
		print(-1)
else:
	ok = True
	for i in range(n):
		if t[(m // n) * i] != s[i]:
			ok = False
			break
	if ok:
		print(m)
	else:
		print(-1)

Submission status: Runtime Error

Solution code:
import math

N, M = map(int, input().split())
S = input()
T = input()

L = int(M*N/math.gcd(N, M))
X = 'A'*int(L)

for i, s in enumerate(S):
    j = int(L/N*i)
    if X[j] == 'A':
        X = X[:j]+s+X[j+1:]
    elif X[j] == s:
        continue
    else:
        print(-1)
        exit(0)

        
for i, t in enumerate(T):
    j = int(L/M*i)
    if X[j] == 'A':
        X = X[:j]+t+X[j+1:]        
    elif X[j] == t:
        continue
    else:
        print(-1)
        exit(0)

print(L)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from fractions import gcd
def inpl(): return list(map(int, input().split()))
N, M = inpl()
S = input()
T = input()

G = N*M // gcd(N, M)

ans = ["*"]*(G)

x = G//N
y = G//M
for n in range(N):
    ans[n*x] = S[n]

for m in range(M):
    if (ans[m*y] == "*") or (ans[m*y] == T[m]):
        ans[m*y] = T[m]
    else:
        print(-1)
        break
else:
    print(G)

Submission status: Runtime Error

Solution code:
import math
n,m = list(map(int, input().split()))
s = input()
t = input()

s1 = ''
for ss in s:
    s1 += ss
    s1 += 'A'*(m-1)

t1 = ''
for tt in t:
    t1 += tt
    t1 += 'A'*(n-1)

ok = 1
for k in range(len(s1)):
    if s1[k] != 'A' and t1[k] != 'A':
        if s1[k] != t1[k]:
            ok = -1
        if ok == -1:
            break
if ok == 1:
    print(int(m * n / math.gcd(m,n)))
else:
    print('-1')

Submission status: Runtime Error

Solution code:
import fraction


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    x = [' '] * n * m
    for i in range(n):
        x[i * m] = s[i]
    for i in range(m):
        if x[i * n] == ' ':
            continue
        if x[i * n] != t[i]:
            print(-1)
            return
    print(n * m // fraction.gcd(n, m))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

n, m = [int(i) for i in input().split()]
S = input()
T = input()

g = n * m // gcd(n, m)

L = [''] * g
if S[0] != T[0]:
    print(-1)
    exit()

for i, s in zip(range(0, g, g//n), S):
    L[i] = s

for i, t in zip(range(0, g, g//m), T):
    L[i] = t
    
A = []
B = []

for i in range(0, g, g//n):
    A.append(L[i])

for i in range(0, g, g//m):
    B.append(L[i])

if ''.join(A) == S and ''.join(B) == T:
    print(g)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math

n, m = map(int, input().split())
s = input().strip()
t = input().strip()

l = m * n //  math.gcd(m, n)


lll = [None] * l

for i in range(0, n-1):
    lll[1+i* l // n] = s[i]


result = True

for i in range(0, m-1):
    if lll[1+i* l // m] == None:
        lll[1+i* l // m] = t[i]
    else:
        if lll[1+i* l // m] != t[i]:
            result = False
            break
if result:
    print(l)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, M = input().split()
S=int(input())
T=int(input())
ans=S*T
print (ans)

Submission status: Runtime Error

Solution code:
import math

N, M = map(int, input().split())
S = input()
T = input()
gcd = math.gcd(N, M)
lcm = N*M//gcd
if N%M==0 or M%N==0:
    exist = True
    if N>M:
        for i in range(M):
            if S[N//M*i]!=T[i]:
                exist = False
                break
    else:
        for i in range(N):
            if T[M//N*i]!=S[i]:
                exist = False
                break
    if exist:
        print(max(N, M))
    else:
        print(-1)
else:
    print(lcm)

Submission status: Runtime Error

Solution code:
import math

def lcm(x, y):
	return (x * y) // math.gcd(x, y)

n, m = map(int, input().split())
s = input()
t = input()

lcm = lcm(n, m)

str1 = ""
str2 = ""
for i in range(lcm):
	str1 += "-"
	str2 += "-"

for i in range(n):
	index = i * lcm // n + 1
	str1 = str1[:index] + s[i] + str1[index+1:]

flg = 0
for i in range(m):
	index = i * lcm // m + 1
	if str1[index:index+1] != "-" and str1[index:index+1] != t[i]:
		print(-1)
		flg = 1
		break

if flg == 0:
	print(lcm)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from fractions import gcd

def solve():
    N, M = map(int, input().split())
    S = list(input())
    T = list(input())

    k = N * M // gcd(N, M)

    S_new = ''.join([c + ' '*(k//N-1) for c in S])
    T_new = ''.join([c + ' '*(k//M-1) for c in T])

    for i, j in zip(S_new, T_new):
        if i !=' ' and j != ' ' and i != j:
            print(-1)
            break
    else:
        print(k)

solve()

Submission status: Runtime Error

Solution code:
from math import gcd

nm = input().split()
n = int(nm[0])
m = int(nm[1])
s = input()
t = input()

ans = int(n*m / gcd(n,m))
for i in range(n):
    if (m*i)%n==0:
        if s[i] != t[(m*i)//n]:
            ans = -1
            
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

nm = input().split()
n = int(nm[0])
m = int(nm[1])
s = input()
t = input()

ans = int(n*m / gcd(n,m))
for i in range(n):
    if (m*i)%n==0:
        if s[i] != t[(m*i)//n]:
            ans = -1
            
print(ans)

Submission status: Runtime Error

Solution code:
import math
def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    x = [' '] * n*m
    for i in range(n):
        x[i*m] = s[i]
    for i in range(m):
        if x[i*n] == ' ':
            continue
        if x[i*n] != t[i]:
            print(-1)
            return
    print(n * m // math.gcd(n, m))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import gcd
N,M = map(int,input().split())
S = input()
T = input()
k = gcd(N,M)
n = N//k
m = M//k
flg = False
for i in range(k):
    if S[n*i] != T[m*i]:
        flg = True
if flg:
    print(-1)
else:
    print(N*m)