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:
from fractions import gcd
def main():
    n, m = list(map(int, input().split(" ")))
    s = input()
    t = input()

    if n < m:
        n, m = m, n
        s, t = t, s

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

    for i in range(lcm(n, m)+1):
        if i == 0:
            continue
        if i % n != 0 or i % m != 0:
            continue

        s_spliters = list(range(0, i, i // n))
        t_spliters = list(range(0, i, i // m))

        flag = True
        count = 0
        for t_spliter in t_spliters:
            if t_spliter in s_spliters:
                index = s_spliters.index(t_spliter)
                if s[index] != t[count]:
                    flag = False
                    break
            count += 1

        if flag:
            print(i)
            return
    print(-1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

s = input()
t = input()

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

lcm = lcm(n,m)

n_ind = []
for i in range(n):
    n_ind.append((lcm / n) * (i))

m_ind = []
for i in range(m):
    m_ind.append((lcm / m) * (i))

ind_list = []
raw_ind_list = n_ind + m_ind
dd_ind_list = list(set(n_ind + m_ind))
for elem in dd_ind_list:
    if raw_ind_list.count(elem) == 2:
        ind_list.append(elem)

flg = True
for i in range(len(ind_list)):
    i_s = int(i / (lcm / n))
    i_t = int(i / (lcm / m))
    if s[i_s] != t[i_t]:
        flg = False
        break

if flg:
    print(int(lcm))
else:
    print(-1)

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()
N = len(S)
M = len(T)
x = gcd(N,M)
Answer = int(N*M/x)

X = [0 for i in range(Answer)]

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

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

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)


S = [ord(c) for c in S]
T = [ord(c) for c in T]

zzz = ord('-')


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


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


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

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


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

print(ret)

Submission status: Time Limit Exceeded

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

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


if S[0] != T[0]:
    print(-1)
    exit()

if len(S) == len(T):
    if S == T:
        print(len(S))
    else:
        print(-1)
    exit()

gcd1 = gcd(len(S), len(T))
lcm = len(S)*len(T) // gcd1

SS = []
TT = []
i = 0
j = 0
while i < N:
    SS.append(i*lcm//N + 1)
    i += 1
while j < M:
    TT.append(j*lcm//M + 1)
    j += 1


for i,v in enumerate(SS):
    if v in TT:
        if S[i] == T[TT.index(v)]:
            continue
        else:
            print(-1)
            exit()
print(lcm)

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 = [0 for i in range(lcm_num)]

for i in range(lcm_num):
    if i == 0 or (i%(lcm_num // N) == 0 and i%(lcm_num // M) == 0):
        if S[i//(lcm_num // N)] == T[i//(lcm_num // M)]:
            continue
        else:
            print(-1)
            exit()

print(lcm_num)

Submission status: Time Limit Exceeded

Solution code:
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(x, y):
    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
        m = lcm(  L // N,  L // M)
        for j in range(1, (L // m) ):
            if S[j * N * m // L] != T[ j * M * m // L]:
                L = -1
                break
        if L == X * i:
            break
    print(L)

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)

import sys
sys.setrecursionlimit(5000000)


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


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


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

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


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

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import re

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

# 最大公約数
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))

#文字列の作成
#SをもとにX
X1 = r''
n = 0
m = 0
ans = 0


for i in range(0,int(L)):
  if i == n * (L//N):
    X1 += S[n]
    n += 1
  else:
    X1 += r'*'
#print(X1)  
#X1とTを比べる

  if i == m * (L//M) :
    #print(i,m,X1[i],T[m])
    if X1[i] == T[m] or X1[i] == "*":
      ans = 1
      m += 1
    else:
      ans = -1
      break

if ans != -1:
  print(int(L))
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())
L = lcm(N,M)
A = []
B = []
flag = 0
counter = 0
for i in range(N) :
    A.append(i*L//N+1)
for j in range(M) :
    b = j*L//M+1
    if b in A :
        index = N*j//M
        if S[index] == T[j] :
            counter += 1
        else :
            flag = 1
    else :
        counter += 1
if flag == 1 :
    print(-1)
else :
    if counter == M :
        print(L)

Submission status: Time Limit Exceeded

Solution code:
def Gcd(a, b):#ユークリッド互除法
	return Gcd(b, a % b) if b else a

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

#最小公倍数
p = (N * M) // Gcd(N, M)
re = p

for i in range(p):
	#交差点
	if i % (p//N) == 0 and i % (p//M) == 0:
		#異なる文字
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
			break
print(re)

Submission status: Time Limit Exceeded

Solution code:
import fractions


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

# よい文字列が存在する場合、答えは最小公倍数となる
l = (n * m) // fractions.gcd(n, m)

# 連結するとSになるXの位置リストを生成
ss = [l // n * i for i in range(n)]
# 連結するとTになるXの位置リストを生成
tt = [l // m * i for i in range(m)]

# 条件を満たすか判定
# for s_num in ss:
#     if s_num in tt:
#         s_idx = ss.index(s_num)
#         t_idx = tt.index(s_num)
#         if s[s_idx] != t[t_idx]:
#             l = -1
#             break

# 共通部分を取得
same = set(ss) & set(tt)
for item in same:
    if s[ss.index(item)] != t[tt.index(item)]:
        l = -1
        break
print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
# 最大公約数
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

# 最小公倍数
def lcm(a, b):
    return a * b / gcd(a, b)

A = list(map(int, input().split()))
N = A[0]
M = A[1]
S = input()
T = input()
# N = 3
# M = 2
# S = 'acp'
# T = 'ae'
S_list = list(S)
T_list = list(T)

# Xの長さ
L = int((lcm(N, M)))

Xn = []
for i in range(N * -1 + 1, 1):
    tmp = (N - 1 + i) * L / N + 1
    Xn.append(int(tmp))

Xm = []
for i in range(M * -1 + 1, 1):
    tmp = (M - 1 + i) * L / M + 1
    Xm.append(int(tmp))

#print(Xn)
#print(Xm)
double_list = list(set(Xn) & set(Xm))
double_list.sort()
#print('double_list', double_list)

Xn_list = []
for i in double_list:
    Xn_list.append(Xn.index(i) + 1)

Xm_list = []
for i in double_list:
    Xm_list.append(Xm.index(i) + 1)

#print(Xn_list)
#print(Xm_list)

flag = False
for xn, xm in zip(Xn_list, Xm_list):
    #print(S_list[xn - 1])
    #print(T_list[xm - 1])

    if S_list[xn - 1] == T_list[xm - 1]:
        #print("同じだ！")
        pass
    else:
        #print("違うだ！")
        flag = True
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
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))

a=["A" for i in range(l)]

for i in range(n):
    a[int(l/n)*i]=s[i]

for i in range(m):
    if a[int(l/m)*i]!="A" and a[int(l/m)*i]!=t[i]:
        print(-1)
        sys.exit()
    
print(l)

Submission status: Time Limit Exceeded

Solution code:
import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
aa=m/gg
bb=n/gg
ab=(m/gg)*(n/gg)
result = ll
i=0
while i < ll :
    if not (i % ab):
            tmp1=i/aa
            tmp2=i/bb
            if s[tmp1] != t[tmp2] :
                result= -1
    i+=1
print result

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)

import sys
sys.setrecursionlimit(500000)


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)


L = maxkobai(N, M)
ret = L
x = {}

for l in range(0, L + 1):
    x[l] = '-'


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
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

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
j = 0
m = 0

for i in range(L):
    if i == 0:
        if S[0] == T[0]:
            r[i] = S[i]
            j += 1
            m += 1
            continue
        else:
            f = True
            break

    if i % s_step == 0 and j < N:
        if r[i] == "*":
            r[i] = S[j]
            j += 1
        else:
            if r[i] != S[j]:
                f = True
                break
            else:
                j += 1

    if i % t_step == 0 and m < M:
        if r[i] == "*":
            r[i] = T[m]
            m += 1
        else:
            if r[i] != T[m]:
                f = True
                break
            else:
                m += 1
if f:
    print(-1)
else:
    print(L)

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(x, y):
    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
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X * i:
            break
    print(L)

Submission status: Time Limit Exceeded

Solution code:
def Gcd(a, b):#ユークリッド互除法
	return Gcd(b, a % b) if b else a

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

#最小公倍数
p = (N * M) // Gcd(N, M)
re = p

for i in range(p):
	#交差点
	if i % (p//N) == 0 and i % (p//M) == 0:
		#異なる文字
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
print(re)

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 = [0 for i in range(lcm_num)]

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] == 0 or X[tmp-1] == T[i]:
        continue
    else:
        print(-1)
        exit()

print(lcm_num)

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
j = 0
m = 0

for i in range(L):
    if i == 0:
        if S[0] == T[0]:
            r[i] = S[i]
            j += 1
            m += 1
            continue
        else:
            f = True
            break

    if i % s_step == 0 and j < N:
        if r[i] == "*":
            r[i] = S[j]
            j += 1
        else:
            if r[i] != S[j]:
                f = True
                break
            else:
                j += 1

    if i % t_step == 0 and m < M:
        if r[i] == "*":
            r[i] = T[m]
            m += 1
        else:
            if r[i] != T[m]:
                f = True
                break
            else:
                m += 1

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

Submission status: Time Limit Exceeded

Solution code:
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(x, y):
    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
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X * i:
            break
    print(L)

Submission status: Time Limit Exceeded

Solution code:
import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
aa=m/gg
bb=n/gg
ab=(m/gg)*(n/gg)
result = ll
for i in xrange(ll) :
    if not (i % ab):
            tmp1=i/aa
            tmp2=i/bb
            if s[tmp1] != t[tmp2] :
                result= -1
print result

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 = ["" for i in range(lcm_num)]

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]:
        continue
    else:
        print(-1)
        exit()

print(lcm_num)

Submission status: Time Limit Exceeded

Solution code:
import fractions


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


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

# よい文字列が存在する場合、答えは最小公倍数となる
l = lcm(n, m)

# 連結するとSになるXの位置リストを生成
ss = [l // n * i for i in range(n)]
# 連結するとTになるXの位置リストを生成
tt = [l // m * i for i in range(m)]

# 条件を満たすか判定
for s_num in ss:
    if s_num in tt:
        s_idx = ss.index(s_num)
        t_idx = tt.index(s_num)
        if s[s_idx] != t[t_idx]:
            l = -1
            break
print(l)

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):
                break
            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 == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1

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

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

t = L // N
n = [t * i for i in range(N)]
t = L // M
m = [t * i for i in range(M)]
nm = list(set(n) & set(m))
for i in nm:
    if S[n.index(i)] != T[m.index(i)]:
        L = -1
        break
print(L)

Submission status: Time Limit Exceeded

Solution code:
import math
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(x, y):
    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) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                counter = -1
                break
        if counter == L:
            break
    print(counter)

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)]
x = {}
#x = ['-'] * (L*10)

for l in range(0, L + 1):
    x[l] = '-'


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
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

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()
x = gcd(len(S),len(T))
Answer = int(len(S)*len(T)/x)
X = [0 for i in range(Answer)]

if (x == 1)and(S[0] == T[0]):
    print(Answer)
    exit()

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 = 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(100):
    L = (i+1) * start
    pos_set = {}
    flg = 0

    for j in range(N):
        pos_set[j * (L / N) + 1] = S[j]
    for k in range(M):
        if pos_set.get(k * (L / M) + 1) is not None:
            if pos_set[k * (L / M) + 1] != T[k]:
                flg = 1
                break
    
    if flg == 0:
        ans = L
        break
        
if ans == 0:
    print('-1')
else:
    print(ans)

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):
  if X[(i+1-1)*int(L/M)] == "":
    X[(i+1-1)*int(L/M)] = T[i]
  else:
    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:
n,m = map(int,input().split())
s = input()
t = input()

def gcd(a, b):
    if b > a:
        a,b = b,a
    a,b = b,a % b
    if b == 0:
        return a
    else:
        return gcd(a,b)
def lcm(a, b):
	return a * b // gcd (a, b)

if s[0] != t[0]:
    print(-1)
    exit()
if gcd(n,m) == 1:
    print(lcm(n,m))
    exit()

ans = lcm(n,m)

for i in range(1,ans):
    if i % (ans//n) != 0 or i%(ans//m) != 0:
        continue
    if s[i // (ans//n)] == t[i // (ans//m)]:
        continue
    else:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

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

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

n, m = map(int, input().split())
s = input()
t = input()
if n == m and s == t:
    print(n)
elif max(n, m) % min(n, m) == 0:
    print(-1)
else:
    LCM = lcm(n, m)
    for i in range(1, m + 1):
        L = LCM * i
        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()

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

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

if not s[0] == t[0]:
	print(-1)
	exit()

nl = max(n, m)
while nl < 10**10:
	if nl % n or nl % m:
		nl += 1
		continue
	if not max(((n - 1) * nl / n) + 1, ((m - 1) * nl / m) + 1) <= nl:
		nl += 1
		continue

	nb = True
	nl_x = [""] * nl
	for i in range(1, n - 1):
		nl_x[int((i * nl / n) + 1)] = s[i]
	for j in range(1, m - 1):
		if not nl_x[int((j * nl / m) + 1)] or nl_x[int((j * nl / m) + 1)] == t[j]:
			nl_x[int((j * nl / m) + 1)] = t[j]
		else:
			nb = False
			break
	else:
		if nb:
			print(nl)
			exit()
	nl += 1
print(-1)

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 = []
    t_list = []
    s_len = range(len(s))
    t_len = range(len(t))
    if len(s) >= len(t):
        for i,(j, k) in enumerate(zip(s_len, list(t_len) + [None]* (len(s_len) - len(t_len)))):
            if not i >= n:
                num_list.append(int((i ) * (l / n) + 1))
            if not i >= m:
                t_list.append(int((i ) * (l / m) + 1))
    else:
         for i,(j, k) in enumerate(zip(list(s_len) + [None]* (len(t_len) - len(s_len)), t_len)):
            if not i >= n:
                num_list.append(int((i ) * (l / n) + 1))
            if not i >= m:
                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 > 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)]

if (gcd(len(S),len(T)) == 1)and(S[0] == T[0]):
    print(Answer)
    exit()

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:
import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
aa=m/gg
bb=n/gg
result = ll
for i in xrange(ll) :
    if not (i % aa):
        tmp1=i/aa
        if not(i % bb) :
            tmp2=i/bb
            if s[tmp1] != t[tmp2] :
                result= -1
print result

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 == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

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)

def cmp(x, y, l):
	if len(x) < len(y):
		x, y = y, x
	lx = int(l/len(x))
	ly = int(l/len(y))
	for i in range(l):
		if i%lx == 0 and i%ly == 0 and x[int(i/lx)] != y[int(i/ly)]:
			return False
	return True

if __name__ == '__main__':
	N, M = list(map(int, input().split()))
	S = input()
	T = input()
	L = lcm(N,M)
	if not cmp(S,T,L):
		print(-1)
	else:
		print(L)

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) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                counter = -1
                break
        if counter == L:
            break
    print(counter)

Submission status: Time Limit Exceeded

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

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

if S[0] != T[0]:
    print(-1)
    exit(0)
if S == T:
    print(N)
    exit(0)

L = lcm(N,M)
p = L//N
q = L//M
U = ""
k = 0

if gcd(M,N) > 1:
    for k in range(1,L):
        if k%p == 0 and k%q == 0:
            if S[k//p] != T[k//q]:
                print(-1)
                exit(0)
    print(L)
else:
    print(L)

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)]
#x = ['-'] * (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
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

Submission status: Time Limit Exceeded

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

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

l = n * m // gcd(n, m)
a = l // n
b = l // m
#print(a, b)
#a(i-1) = b(j-i) -> ai = bj + (a-b)
res = False
clear_all = True
for i in range(1,n+1):
    for j in range(1,m+1):
        if a * i - b * j == a - b:
            if not s[i-1] == t[j-1]:
                clear_all = False
if clear_all:
    res = True
if res:
    print(l)
else:
    print(-1)

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(1000):
    L = (i+1) * start
    pos_dic = {}
    ng_flg = 0
  
    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:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

n = []
for i in range(N):
    n.append(L // N * i)
m = []
for i in range(M):
    m.append(L // M * i)
nm = list(set(n) & set(m))
for i in nm:
    if S[n.index(i)] != T[m.index(i)]:
        L = -1
        break
print(L)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import itertools
import math

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

    if N < M:
        t = M
        M = N
        N = t
        q = S
        S = T
        T = q

    ret = -1
    for step in range(1, M+1):
        slen = step * N
        if slen % M != 0:
            continue
        mstep = slen // M
        good = True
        for i in range(N):
            u = (step * i) % mstep
            if u != 0:
                continue
            j = (step * i) // mstep
            if S[i] != T[j]:
                good = False
                break
        if good:
            ret = step * N
            break

    # 出力
    print("{}".format(ret))


if __name__ == '__main__':
    main()