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: Time Limit Exceeded

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

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

def cal(S,T,N,M):
    for i in range(N):
        for j in range(M):
            if(i*M==j*N):
                if(S[i]!=T[j]):
                    return -1
    return lcm(N,M)
N,M=list(map(int,input().split()))
S=input()
T=input()
print(cal(S,T,N,M))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
S = str(input())
T = str(input())

def lcm(x, y):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    return (x * y) // gcd(x, y)
X = lcm(N ,M)

if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)

else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        counter = L
        y = L // N
        z = L // M
        match = lcm( y, z)
        for j in range(1, (L // match) ):
            k = j * N * match // L
            l = j * M * match // L
            if S[k] != T[l]:
                counter = -1
        if counter == L:
            break
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    for i in range(N):
        for j in range(M):
            if((i-1)*k/N+1 == (j-1)*k/M+1):
                if(S[i-1] != T[j-1]):
                    flag = 0
                    count += 1
                    break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd


N, M = list(map(int, input().split()))
S = input()
T = input()
N = len(S)
M = len(T)
s = []
t = []
x = []
L = int(N * M / gcd(N, M))


for i in range(L):
    x.append(0)

tmplen = N if N >= M else M

if tmplen == N:
    for i in range(tmplen):
        num = int(i * (L / N))
        x[num] = S[i]
    otherlen = M
    for j in range(otherlen):
        num = int(j * (L/M))
        if x[num] != 0 and x[num] != T[j]:
            L = -1
            break
else:
    for i in range(tmplen):
        num = int(i * (L / M))
        x[num] = T[i]
    otherlen = N
    for j in range(otherlen):
        num = int(j * (L/N))
        if x[num] != 0 and x[num] != S[j]:
            L = -1
            break
print(L)

Submission status: Time Limit Exceeded

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

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

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

lcm_num = lcm(N,M)

# X_s = ["" for i in range(lcm_num)]
# X_t = ["" for i in range(lcm_num)]
X = ["" for i in range(lcm_num)]

# print(X_s,X_t)

for i in range(N):
    tmp = i*lcm_num // N + 1
    X[tmp-1] = S[i]


for i in range(M):
    tmp = i*lcm_num // M + 1
    if X[tmp-1] == "" or X[tmp-1] == T[i]:
        pass
    else:
        print(-1)
        exit()

print(lcm_num)

Submission status: Time Limit Exceeded

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

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

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

lcm_num = lcm(N,M)

# X_s = ["" for i in range(lcm_num)]
# X_t = ["" for i in range(lcm_num)]
X = ["" for i in range(lcm_num)]

# print(X_s,X_t)

for i in range(N):
    tmp = i*lcm_num // N + 1
    X[tmp-1] = S[i]


for i in range(M):
    tmp = i*lcm_num // M + 1
    if X[tmp-1] == "" or X[tmp-1] == T[i]:
        pass
    else:
        print(-1)
        exit()

print(lcm_num)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


def gcd(a, b):
    if (a < b):
        return gcd(b, a)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def maxkobai(a, b):
    return a * b // gcd(a, b)


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
x = ['-' for i in range(L+1)]

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    if x[idx] != '-':
        if (x[idx] != T[m]):
            ret = -1
            break

print(ret)

Submission status: Time Limit Exceeded

Solution code:

n, m = map(int, input().split())
listS = list(input())
listT = list(input())
listX = []


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

l= n*m // gcd(n, m)
a=l//n
b=l//m

if listS[0]!=listT[0]:
    print(-1)
else:
    index =0
    index2=0
    while index < l:
        while index2 < n:
            if index == index2*a:
                listX.append(listS[index2])
                index2+=1
                index+=1
            else:
                listX.append(0)
                index+=1
        index+=1
    index4=0
    flag=0
    while index4 < min(m, l//b):
        if listX[index4*b] == listT[index4] or listX[index4*b] == 0:
            index4+=1
        else:
            print(-1)
            flag=1
            break
    if flag!=1:
        print(l)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd


N, M = list(map(int, input().split()))
S = input()
T = input()
N = len(S)
M = len(T)
s = []
t = []
x = []
L = int(N * M / gcd(N, M))


for i in range(L):
    x.append(0)

tmplen = N if N >= M else M

if tmplen == N:
    for i in range(tmplen):
        num = int(i * (L / N))
        x[num] = S[i]
    otherlen = M
    for j in range(otherlen):
        num = int(j * (L/M))
        if x[num] != 0 and x[num] != T[j]:
            L = -1
else:
    for i in range(tmplen):
        num = int(i * (L / M))
        x[num] = T[i]
    otherlen = N
    for j in range(otherlen):
        num = int(j * (L/N))
        if x[num] != 0 and x[num] != S[j]:
            L = -1

print(L)

Submission status: Time Limit Exceeded

Solution code:

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


def get_gcd(a, b):
    if a < b:
        a, b = b, a

    if a % b == 0:
        return b
    else:
        return get_gcd(b, a % b)


def get_lcm(a, b, gcd):
    lcm = a * b // gcd
    return lcm


start = get_lcm(N, M, get_gcd(N, M))
ans = 0
for i in range(10000):
    L = (i+1) * start
    pos_dic = {}
    ng_flg = 0

    if L < (N - 1) * (L / N) + 1 or L < (M - 1) * (L / M) + 1:
        continue

    for j, s in enumerate(S):
        pos_dic[j * (L / N) + 1] = s
    for k, t in enumerate(T):
        if pos_dic.get(k * (L / M) + 1, None) is None:
            pass
        else:
            if pos_dic[k * (L / M) + 1] == t:
                pass
            else:
                ng_flg = 1
                break

    if ng_flg == 0:
        ans = L
        break

if ans == 0:
    print('-1')
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

#LがM,Nの最小公倍数の場合を調べる
L = int((N*M)/fractions.gcd(N,M))
#L文字の文字列用
X = ['0' for i in range(L)]

#2番目の条件を満たすようにSをXにはめ込む
for i in range(N):
    X[int((L/N)*i)] = S[i]

#3番目の条件についての判定
#Xの1,L/M+1...文字目がTと同じまたは0ならXは「よい文字列」
for j in range(M):
    if (X[int((L/M)*j)] != T[j]) and (X[int((L/M)*j)] != '0'):
        flg = False

if flg == True:
    print(L)
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


def gcd(a, b):
    if (a < b):
        return gcd(b, a)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def maxkobai(a, b):
    return a * b // gcd(a, b)


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
x = ['-' for i in range(L+1)]

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    if x[idx] != '-':
        if (x[idx] != T[m]):
            ret = -1

print(ret)

Submission status: Time Limit Exceeded

Solution code:
def gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

N, M=map(int, input().split())
S=input()
T=input()
gcd=gcd(N,M)
lcm=N*M//gcd
counter=0

X_S=[1+i*(lcm/N) for i in range(N)]
X_T=[1+i*(lcm/M) for i in range(M)]

X_ST_set=list(set(X_S) & set(X_T))

if len(X_ST_set)==0:
    print(int(lcm))
else:
    for i in X_ST_set:
        X_S_index=X_S.index(i)
        X_T_index=X_T.index(i)
        if S[X_S_index]!=T[X_T_index]:
            counter+=1

    if counter==0:
        print(int(lcm))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(m,n) :
    x = max(m,n)
    y = min(m,n)
    if x%y == 0 :
        return y
    else :
        while x%y != 0 :
            z = x%y
            x = y
            y = z
        else :
            return z

def lcm(m,n) :
    return int(m*n/gcd(m,n))

N,M = map(int,input().split())
S = list(input())
T = list(input())
A = []
B = []
counter = 0
if N % M == 0 or S[0] != T[0] :
    print(-1)
else :
    L = lcm(N,M)
    for i in range(N) :
        A.append(i*L//N+1)
    for j in range(M) :
        B.append(j*L//M+1)
for k in range(len(B)) :
    if B[k] in A :
        for x in range(len(A)) :
            if A[x] == B[k] :
                a = A[k]
        if S[k] == a :
            break
        else :
            counter += 1
    else :
        counter += 1
if counter == len(B) and len(B) != 0 :
    print(L)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math


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


N, M = list(map(int, input().split()))
S = input()
T = input()
N = len(S)
M = len(T)
s = []
t = []
x = []
L = int(N * M / gcd(N, M))


for i in range(L):
    x.append(0)

tmplen = N if N >= M else M

if tmplen == N:
    for i in range(tmplen):
        num = int(i * (L / N))
        x[num] = S[i]
    otherlen = M
    for j in range(otherlen):
        num = int(j * (L/M))
        if x[num] != 0 and x[num] != T[j]:
            L = -1
else:
    for i in range(tmplen):
        num = int(i * (L / M))
        x[num] = T[i]
    otherlen = N
    for j in range(otherlen):
        num = int(j * (L/N))
        if x[num] != 0 and x[num] != S[j]:
            L = -1

print(L)

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split(" "))
S = input()
T = input()
Answer = int(len(S)*len(T)/gcd(len(S),len(T)))
X = [0 for i in range(Answer)]

for i in range(len(S)):
    X[int(i*Answer/len(S))] = S[i]

for i in range(len(T)):
    if (X[int(i*Answer/len(T))] == 0)or(X[int(i*Answer/len(T))] == T[i]):
        continue
    else:
        print(-1)
        exit()
print(Answer)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
t = input()
def calc(n, m, s, t):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    def lcm(a, b):
        return a * b // gcd (a, b)

    l = lcm(n, m)

    num_list = []
    for i, j in enumerate(range(len(s))):
        if i == n:
            break
        num_list.append(int((i ) * (l / n) + 1))
    t_list = []
    for i, j in enumerate(range(len(t))):
        if i == m:
            break
        t_list.append(int((i ) * (l / m) + 1))
    
    check_list = (set(num_list) & set(t_list))
    for i in check_list:
        if s[num_list.index(i)] != t[t_list.index(i)]:
            return -1
    else:
        return l
print(calc(n, m, s, t))

Submission status: Time Limit Exceeded

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

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

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

lcm_num = lcm(N,M)

X_s = ["" for i in range(lcm_num)]
X_t = ["" for i in range(lcm_num)]

# print(X_s,X_t)

for i in range(N):
    tmp = i*lcm_num // N + 1
    X_s[tmp-1] = S[i]


for i in range(M):
    tmp = i*lcm_num // M + 1
    X_t[tmp-1] = T[i]

# print(X_s,X_t)

for s,t in zip(X_s,X_t):
    if s == "" or t == "" :
        continue
    elif s == t:
        continue
    else:
        print(-1)
        exit()

print(lcm_num)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
s = input()
t = input()

def gcd(a,b):
    if a<b:
        a,b = b,a
    if b==0:
        return a
    c = a%b
    return gcd(b,c)

def lcm(a,b):
    return a*b//gcd(a,b)

l = lcm(n,m)
ls = ["." for _ in range(l)]

for i in range(n):
    if i*m%n==0:
        j = i*m//n
        if s[i]!=t[j]:
            print(-1)
            exit()
print(l)

# for i in range(n):
#     ls[i*l//n] = s[i]
# for i in range(m):
#     if ls[i*l//m]!="." and ls[i*l//m]!=t[i]:
#         print(-1)
#         exit()
# print(l)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
S = input()
T = input()

gcd = gcd(n, m)
L = int(n * m / gcd)

a = int(L/n)
b = int(L/m)

flag=True

for i in range(L):
    if (int(i%a) == 0 and int(i%b) == 0):
        if not S[int(i/a)] == T[int(i/b)]:
            flag = False
if flag:
    print(L)
else:
    print("-1")

Submission status: Time Limit Exceeded

Solution code:
def gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

N, M=map(int, input().split())
S=input()
T=input()
gcd=gcd(N,M)
lcm=N*M//gcd
counter=0

X_S=[1+i*(lcm/N) for i in range(N)]
X_T=[1+i*(lcm/M) for i in range(M)]

X_ST_set=list(set(X_S) & set(X_T))

if len(X_ST_set)==0:
    print(int(lcm))
else:
    for i in X_ST_set:
        X_S_index=X_S.index(i)
        X_T_index=X_T.index(i)
        if S[X_S_index]!=T[X_T_index]:
            print(-1)
            break
        counter+=1

    if counter==len(X_ST_set):
        print(int(lcm))

Submission status: Time Limit Exceeded

Solution code:
# from math import gcd
from fractions import gcd

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


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

if N > M:
  N, M = M, N
  S, T = T, S

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  if L == N*M:
    break

print(-1)

Submission status: Time Limit Exceeded

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)

try:

    L = ['' for i in range(g)]

except:
    print(-1)
    exit()

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: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
S = input()
T = input()

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

def lcm(a, b):
	return a * b // gcd (a, b)

ans = lcm(N, M)

i = 0
res = [0 for i in range(ans)]

for i in range(N):
    tmp_s = int(ans/N) * i
    res[tmp_s] = S[i]

for j in range(M):
    tmp_t = int(ans/M) * j
    if res[tmp_t] != 0:
        if T[j] != res[tmp_t]:
            ans = -1

print(ans)

Submission status: Time Limit Exceeded

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

while True:
    try:
        if l % n == 0 and l % m == 0:
            a = [None] * l
            ln = l // n
            for i in range(n):
                a[ln * i] = s[i]
            lm = l // m
            for i in range(m):
                if not (a[lm * i] == None or a[lm * i] == t[i]):
                    raise Exception
            break
    except:
        None
    if l < n * m:
        l = l + 1
    else:
        l = -1
        break
print(l)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int,input().split())
    s = input()
    t = input()

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

    nlist = [0 for i in range(n)]
    mlist = [0 for i in range(m)]
    for i in range(n):
        nlist[i] =  i*l//n

    for i in range(m):
        mlist[i] =  i*l//m

    src_set = set(nlist)
    tag_set = set(mlist)
    matched_list = list(src_set.intersection(tag_set))

    for i in matched_list:
        s_index = nlist.index(i)
        t_index = mlist.index(i)

        if s[s_index] != t[t_index]:
            print("-1")
            exit()

    print(l)

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

if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split(" "))
S = input()
T = input()

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

def lcm(a, b):
	return a * b // gcd (a, b)

L = lcm(N, M)
LparN = L / N
LparM = L / M

listN = []
listM = []

flag = 0

for i in range(N):
  indexN = i * LparN + 1
  listN.append([indexN, S[i]])
for j in range(M):
  indexM = j * LparM + 1
  listM.append([indexM, T[j]])

for k in range(len(listN)):
  for l in range(len(listM)):
    if listN[k][0] == listM[l][0]:
      if listN[k][1] != listM[l][1]:
        flag = 1
        break
      
  
if flag == 0:
  print(L)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
	if a > b:
		a, b = b, a
	if a % b == 0:
		return b
	while a % b != 0:
		c = a% b
		a = b
		b = c
	else:
		return c

def lcmCalc(x, y):
	return (x * y) // gcd(x, y)

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

lcm = lcmCalc(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: Time Limit Exceeded

Solution code:
def gcd(a, b):
	if a > b:
		a, b = b, a
	if a % b == 0:
		return b
	while a % b != 0:
		c = a% b
		a, b = b, c
	else:
		return c

def lcmCalc(x, y):
	return (x * y) // gcd(x, y)

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

lcm = lcmCalc(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: Time Limit Exceeded

Solution code:
def gcd(N,M):
    while True:
        if min(N,M)==0:
            return max(N,M)
        elif N>M:
            N%=M
        elif M>N:
            M%=N
def lcm(N,M):
    return N*M//gcd(N,M)

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

L=lcm(N,M)

for i in range((N*M)//L):
    if S[i*L//M]!=T[i*L//N]:
        L=-1
        break
print(L)

Submission status: Time Limit Exceeded

Solution code:
# A
n,m = map(int, input().split())
s = str(input())
t = str(input())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a,b):
    return a*b/gcd(a,b)
l=int(lcm(n,m))
ss = [i for i in range(1,l+1,int(l/n))]
# print(ss)
tt = [i for i in range(1,l+1,int(l/m))]
# print(tt)
ii = list(set(ss)&set(tt))
# print(ii)
for x in ii:
    if s[ss.index(x)] != t[tt.index(x)]:
        print('-1')
        break
else:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
	if a > b:
		a, b = b, a
	if a % b == 0:
		return b
	while a % b != 0:
		c = a% b
		a, b = b, c
	else:
		return c

def lcmCalc(x, y):
	return int((x * y) / gcd(x, y))

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

lcm = lcmCalc(n, m)

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

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

flg = 0
for i in range(m):
	index = int(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: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
t = input()
def calc(n, m, s, t):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    def lcm(a, b):
        return a * b // gcd (a, b)

    l = lcm(n, m)

    num_list = []
    for i, j in enumerate(range(len(s))):
        if i == n:
            break
        num_list.append(int((i ) * (l / n) + 1))
    t_list = []
    for i, j in enumerate(range(len(t))):
        if i == m:
            break
        num_list.append(int((i ) * (l / m) + 1))
        t_list.append(int((i ) * (l / m) + 1))

    check_list = [x for x in set(num_list) if num_list.count(x) > 1]

    for i in check_list:
        if s[num_list.index(i)] != t[t_list.index(i)]:
            return -1
    else:
        return l
print(calc(n, m, s, t))

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    while y!= 0:
        x, y=y, x%y
    return x

N, M=map(int, input().split())
S=input()
T=input()
gcd=gcd(N,M)
lcm=N*M/gcd
counter=0

X_S=[int(1+i*(lcm/N)) for i in range(N)]
X_T=[int(1+i*(lcm/M)) for i in range(M)]

X_ST_set=list(set(X_S) & set(X_T))

if len(X_ST_set)==0:
    print(int(lcm))
else:
    for i in X_ST_set:
        X_S_index=X_S.index(i)
        X_T_index=X_T.index(i)
        if S[X_S_index]!=T[X_T_index]:
            print(-1)
            break
        counter+=1

    if counter==len(X_ST_set):
        print(int(lcm))

Submission status: Time Limit Exceeded

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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    r = a % b
    return gcd(b, r)

def lcm(a,b):
  return int(a*b/gcd(a,b))

X = ["" for i in range(lcm(N,M))]
L = len(X)
flag = True

for i in range(N):
  X[(i+1-1)*int(L/N)] = S[i]

for i in range(M):
  X[(i+1-1)*int(L/M)] = T[i]

for i in range(N):
  if X[(i+1-1)*int(L/N)] == S[i]:
    continue
  else:
    flag = False
    break
if flag:
  for i in range(M):
    if X[(i+1-1)*int(L/M)] == T[i]:
      continue
    else:
      flag == False
      break

if flag:  
  print(L)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N, M = list(map(int, input().split()))
S = input()
T = input()

L = int(N * M / fractions.gcd(N, M))
LN = int(L / N)
LM = int(L / M)

count = 0
dic1 = {LN*n:S[n] for n in range(N)}
dic2 = {LM*n:T[n] for n in range(M)}

for n in range(L):
    if (n in dic1) and (n in dic2) and dic1[n] != dic2[n]:
        count += 1
        break

if count == 0:
    print(L)
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
S = input()
T = input()

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

def lcm(a, b):
	return a * b // gcd (a, b)

ans = lcm(N, M)

i = 0
res = [0 for i in range(ans)]

for i in range(N):
    tmp_s = int(ans/N) * i
    res[tmp_s] = S[i]

for j in range(M):
    tmp_t = int(ans/M) * j
    if res[tmp_t] != 0:
        if T[j] != res[tmp_t]:
            ans = -1

print(ans)

Submission status: Time Limit Exceeded

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

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

l = int(n*m / gcd(n, m))
for i in [1, 2, 3, 5, 7, 11, 13]:
    L = l*i
    for j in range(n):
        for k in range(m):
            if j*L/n + 1 == k*L/m + 1:
                if s[j] == t[k]:
                    flag = True
                else:
                    flag = False
    
    if flag:
        print(L)
        exit()



print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
t = input()
if max(n, m) % min(n, m) == 0:
    print(-1)
else:
    for L in range(n, n * m + 1, n):
        if L % m == 0:
            x = ["" for i in range(L)]
            no = 0
            for i in range(n):
                x[i * L // n] = s[i]
            for i in range(m):
                if x[i * L // m] and x[i * L // m] != t[i]:
                    no = 1
                    break
                else:
                    x[i * L // m] = t[i]
            if no:
                continue
            print(L)
            exit()
    print(-1)

Submission status: Time Limit Exceeded

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


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    else:
        return a if b == 0 else gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(b, a%b)


L = lcm(N, M)

r = ["*" for i in range(L)]
s = 0
t = 0
f = False

s_step = L // N
t_step = L //M
i = 0
j = 0
while s < L:
    r[s] = S[i]
    s += s_step
    i += 1


while t < L:
    if r[t] == T[j]:
        t += t_step
        j += 1
        continue
    elif r[t] == "*":
        r[t] = T[j]
        t += t_step
        j += 1
    else:
        f = True
        break
if f:
    print(-1)
else:
    print(L)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    while y!= 0:
        x, y=y, x%y
    return x

N, M=map(int, input().split())
S=input()
T=input()
gcd=gcd(N,M)
lcm=N*M/gcd
counter=0

X_S=[int(1+i*(lcm/N)) for i in range(N)]
X_T=[int(1+i*(lcm/M)) for i in range(M)]

X_ST_set=sorted(list(set(X_S) & set(X_T)))

if len(X_ST_set)==0:
    print(int(lcm))
else:
    for i in X_ST_set:
        X_S_index=X_S.index(i)
        X_T_index=X_T.index(i)
        if S[X_S_index]!=T[X_T_index]:
            print(-1)
            break
        counter+=1

    if counter==len(X_ST_set):
        print(int(lcm))

Submission status: Time Limit Exceeded

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

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

re = -1
# 1文字目が必ず一緒であること
if S[0] == T[0]:
    min_num = (N * M)  // gcd(N, M) # 最小公倍数を求める（基本はこれが答え）
    re = min_num
    # 重なる部分が同じ文字かを調べる
    s_d = min_num // N
    t_d = min_num // M
    # 最小公倍数みる
    st_min = (s_d * t_d) // gcd(s_d, t_d)
    st = st_min
    while st < N and st < M:
        if S[st // (min_num // N)] != T[st // (min_num // M)]:
            re = -1
            break

print(re)

Submission status: Time Limit Exceeded

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

l = 1
while (True):
    if l % n == 0 and l % m == 0:
        x = [""] * l
        isOK = True
        for nn in range(n):
            x[int(nn * l / n)] = s[nn]
        for mm in range(m):
            # x[int(mm * l / m)] = t[mm]
            if x[int(mm * l / m)] != t[mm] and x[int(mm * l / m)] != "":
                x[int(mm * l / m)] = t[mm]
                isOK = False
                break
            

        if isOK:
            print(l)
            break
    
    l += 1

    if l > n * m:
        print("-1")
        break

Submission status: Time Limit Exceeded

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

def lcmCalc(x, y):
	return int((x * y) / gcd(x, y))

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

lcm = lcmCalc(n, m)

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

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

flg = 0
for i in range(m):
	index = int(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: Time Limit Exceeded

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

a = ""
b = ""
c = 1

import fractions

def lcm(x, y):
    return (x * y) // fractions.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: Time Limit Exceeded

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()

# L はNとMのどちらでも割り切れる
# Xの1, L/N + 1 , 2 *  L/N + 1, ... (N-1) * L/N + 1の文字列を連結するとS 長さはN
# Xの1, L/M + 1 , 2 *  L/M+ 1, ... (M-1) * L/M + 1の文字列を連結するとT 長さはM

re = -1
# 1文字目が必ず一緒であること
if S[0] == T[0]:
    min_num = (N * M)  // gcd(N, M) # 最小公倍数を求める（基本はこれが答え）
    re = min_num
    # 重なる部分が同じ文字かを調べる
    s_d = min_num // N
    t_d = min_num // M
    # 最小公倍数みる
    st_min = (s_d * t_d) // gcd(s_d, t_d)
    st = st_min
    while st < N and st < M:
        if S[st // (min_num // N)] != T[st // (min_num // M)]:
            re = -1
            break

print(re)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split(" ")))
s = input()
t = input()
if n<m:
  s, t = t, s
  n, m = m, n
def gcd(a,b):
  while b > 0:
    a, b = b, a % b
  return a
d = gcd(n, m)
l = n*m // d
a = ['' for i in range(l)]
res = l
for i in range(n):
  a[i*(l//n)] = s[i]
for i in range(m):
  if a[i*(l//m)]!='' and a[i*(l//m)]!=t[i]:
    res = -1
    break
print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from collections import defaultdict
N, M = list(map(int, input().split()))
S = input()
T = input()

L = int(N * M / fractions.gcd(N, M))
LN = int(L / N)
LM = int(L / M)

count = 0
dic1 = defaultdict(int)
dic2 = defaultdict(int)
for n in range(N):
    dic1[LN*n] = S[n]

for n in range(M):
    dic2[LM*n] = T[n]

for n in range(L):
    if dic1[n] != 0 and dic2[n] != 0 and dic1[n] != dic2[n]:
        count += 1
        break

if count == 0:
    print(L)
else:
    print('-1')