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:
import numpy as np

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

# 最大公約数を求める関数
def gcd(a,b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

# 最小公倍数を求める関数
def lcm(a,b):
    return (a*b)/gcd(a,b)

# 最初の文字が異なれば -1 
if s[0] != t[0]:
    print(-1)
elif s == t:
    print(len(s))
else:
    # check variable
    # check = True
    # iter = 1
    LeastCommonMultiple  = lcm(n,m)
    # l は n,m によって割り切れて正数商を持たなければならない
    # よってnとmの公倍数でなければいけない
    # while check:
    l = int(LeastCommonMultiple)
    nOl = l // n
    mOl = l // m
    # sinX = np.array([i * nOl + 1 for i in range(n)])
    # tinX = np.array([i * mOl + 1 for i in range(m)])
    sinX = [i * nOl + 1 for i in range(n)]
    tinX = [i * mOl + 1 for i in range(m)]
    matchList = list(set(sinX) & set(tinX))
    
    # if len(matchList) == 0:
    #     continue

    # scX = [np.where(sinX == commonIndex)[0][0] for commonIndex in matchList]
    # tcX = [np.where(tinX == commonIndex)[0][0] for commonIndex in matchList]

    scX = [sinX.index(commonIndex) for commonIndex in matchList]
    tcX = [tinX.index(commonIndex) for commonIndex in matchList]

    # import ipdb; ipdb.set_trace()

    if [s[sMatch] for sMatch in scX] == [t[tMatch] for tMatch in tcX]:
        # check = False
        # matchFlag = True
        print(l)
    else:
        # check = False # here
        # matchFlag = False
        print(-1)
    
    # if iter == min(len(s), len(t)):
    #     check = False
    #     matchFlag = False

    # iter += 1

    # if matchFlag:
    #     print(l)
    # else:
    #     print(-1)

Submission status: Time Limit Exceeded

Solution code:
import fractions
 
n, m = (int(i) for i in input().split()) 
 
s = input()
t = input()
 
lcm = n * m / fractions.gcd(n, m)

k = max(n,m)
l = min(n,m)

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

ind_list = []
for i in range(k):
    if n_ind.count((lcm / k) * (i)) == 1:
        ind_list.append((lcm / k) * (i))
 
flg = True
for i in range(len(ind_list)):
    if s[int(i / (lcm / n))] != t[int(i / (lcm / m))]:
        flg = False
        break
 
if flg:
    print(int(lcm))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import fractions
 
n, m = (int(i) for i in input().split()) 
 
s = input()
t = input()
 
lcm = n * m / fractions.gcd(n, m)
 
n_ind = []
for i in range(n):
    n_ind.append((lcm / n) * (i))

ind_list = []
for i in range(m):
    if n_ind.count((lcm / m) * (i)) == 1:
        ind_list.append((lcm / m) * (i))
 
flg = True
for i in range(len(ind_list)):
    if s[int(i / (lcm / n))] != t[int(i / (lcm / m))]:
        flg = False
        break
 
if flg:
    print(int(lcm))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def pdbg(label, val):
    # print("[%s]%s" % (label, val))
    pass


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


pNM = N / M
pMN = M / N


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


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


def is_unique(seq):
    return len(seq) == len(set(seq))


def calculate(lenv):
    ln = int(lenv / N)
    lm = int(lenv / M)

    pdbg('L', lenv)
    pdbg('N', N)
    pdbg('M', M)
    pdbg('LN', ln)
    pdbg('LM', lm)

    l_ns = []
    for i in range(0, N, ln):
        l_ns.append(i)
    pdbg('LNs', l_ns)
    l_ms = []
    for j in range(0, M, lm):
        l_ms.append(j)
    pdbg('LMs', l_ms)
    dpl = (set(l_ns) & set(l_ms))
    pdbg('dpl', dpl)
    if pNM == round(pNM) or pMN == round(pMN):
        return -1
    if S[0] != T[0]:
        return -1
    for k in dpl:
        pdbg('k', k)
        pdbg('Sk', S[k])
        pdbg('Tk', T[k])
        if S[k] != T[k]:
            return -1
    return lenv


def cml():
    lms = lcm(N, M)
    while lms < 99999000000:
        res = calculate(lms)
        if res == -1:
            continue
        else:
            return lms


print(cml())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# 最大公約数を求める関数
def gcd(a,b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

# 最小公倍数を求める関数
def lcm(a,b):
    return (a*b)/gcd(a,b)

# 最初の文字が異なれば -1 
if s[0] != t[0]:
    print(-1)
elif s == t:
    print(len(s))
else:
    # check variable
    check = True
    iter = 1
    LeastCommonMultiple  = lcm(n,m)
    # l は n,m によって割り切れて正数商を持たなければならない
    # よってnとmの公倍数でなければいけない
    while check:
        l = int(LeastCommonMultiple*iter)
        nOl = l // n
        mOl = l // m
        sinX = np.array([i * nOl + 1 for i in range(n)])
        tinX = np.array([i * mOl + 1 for i in range(m)])
        matchList = list(set(sinX) & set(tinX))
        
        if len(matchList) == 0:
            continue

        scX = [np.where(sinX == commonIndex)[0][0] for commonIndex in matchList]
        tcX = [np.where(tinX == commonIndex)[0][0] for commonIndex in matchList]

        # import ipdb; ipdb.set_trace()

        if [s[sMatch] for sMatch in scX] == [t[tMatch] for tMatch in tcX]:
            check = False
            matchFlag = True
        else:
            check = False # here
            matchFlag = False
        
        # if iter == min(len(s), len(t)):
        #     check = False
        #     matchFlag = False

        iter += 1

    if matchFlag:
        print(l)
    else:
        print(-1)

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):
            hoge = i*k/N+1
            fuga = j*k/M+1
            if(hoge < fuga):
                break
            elif(hoge == fuga):
                if(S[i] != T[j]):
                    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:
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
 
#list内包にしたらはやいのかな？
for i in range(0,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] == "*":
      m += 1
    else:
      print(-1)
      exit()
 
print(int(L))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# 最大公約数を求める関数
def gcd(a,b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

# 最小公倍数を求める関数
def lcm(a,b):
    return (a*b)/gcd(a,b)

# 最初の文字が異なれば -1 
if s[0] != t[0]:
    print(-1)
else:
    # check variable
    check = True
    iter = 1
    LeastCommonMultiple  = lcm(n,m)
    # l は n,m によって割り切れて正数商を持たなければならない
    # よってnとmの公倍数でなければいけない
    while check:
        l = int(LeastCommonMultiple*iter)
        nOl = l // n
        mOl = l // m
        sinX = np.array([i * nOl + 1 for i in range(n)])
        tinX = np.array([i * mOl + 1 for i in range(m)])
        matchList = list(set(sinX) & set(tinX))
        
        if len(matchList) == 0:
            continue

        scX = [np.where(sinX == commonIndex)[0][0] for commonIndex in matchList]
        tcX = [np.where(tinX == commonIndex)[0][0] for commonIndex in matchList]

        # import ipdb; ipdb.set_trace()

        if [s[sMatch] for sMatch in scX] == [t[tMatch] for tMatch in tcX]:
            check = False
            matchFlag = True
        else:
            matchFlag = False
        
        # if iter == min(len(s), len(t)):
        #     check = False
        #     matchFlag = False

        iter += 1

    if matchFlag:
        print(l)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

alphabet = [chr(i) for i in range(97, 97 + 26)]


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


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

# Generate x canditate
x_len = lcm(n, m)
canditates_s = ["" for i in range(x_len)]
canditates_t = ["" for i in range(x_len)]
s_indlist = [i * int(x_len / n) for i in range(n)]
t_indlist = [i * int(x_len / m) for i in range(m)]
for i, s_ind in enumerate(s_indlist):
    canditates_s[s_ind] = s[i]
for i, t_ind in enumerate(t_indlist):
    canditates_t[t_ind] = t[i]

# Shared set
shared_set = set(s_indlist) & set(t_indlist)
    
# Djudge incoherence
for i in shared_set:
    if canditates_s[i] != canditates_t[i]:
        print(-1)
        exit()

# If the djudge cleared
print(x_len)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math


def run(n, m, s, t):
    ret = -1
    if s[0] != t[0]:
        return ret
    g = fractions.gcd(n, m)
    if g == 1:
        big = max([n, m])
        small = min([n, m])
        if small == 1:
            for i in range(math.sqrt(n)):
                if big % i == 0:
                    return i
        else:
            return n*m
    n_s = n//g
    m_s = m//g
    mn = n_s * m_s
    small = min([g, mn])
    for j in range(1, g+1):
        n_eval = j*n_s
        m_eval = j*m_s
        eval = True
        for i in range(1, g):
            if i*n_eval >= n:
                eval = False
                continue
            if i*m_eval >= m:
                eval = False
                continue
            if s[i*n_eval] != t[i*m_eval]:
                eval = False
                continue
        if eval:
            return n_eval * m_eval * g
    return -1


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


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):
    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 my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
ans = 0
fans = ans

_lcm = lcm(len(S), len(T))
for k in list(reversed(range(1, (len(S) * len(T))//_lcm + 1))):
    ans = k * _lcm
    double_st = []
    
    for i in range(len(S)):
        if (len(T)*i)%len(S) == 0 and (len(T) * i)//len(S) <len(T):
            double_st += [(i * ans)//len(S) + 1]
    isImpossible = False

    for st in double_st:
        s_i = ((st-1) * len(S))//ans
        t_i = ((st-1) * len(T))//ans
        if S[s_i] != T[t_i]:
            isImpossible = True
            break

            
    if isImpossible:
        break
    else:
        success = True
        fans = ans

if not success:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# 最大公約数を求める関数
def gcd(a,b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

# 最小公倍数を求める関数
def lcm(a,b):
    return (a*b)/gcd(a,b)

# 最初の文字が異なれば -1 
if s[0] != t[0]:
    print(-1)
else:
    # check variable
    check = True
    iter = 1
    LeastCommonMultiple  = lcm(n,m)
    # l は n,m によって割り切れて正数商を持たなければならない
    # よってnとmの公倍数でなければいけない
    while check:
        l = int(LeastCommonMultiple*iter)
        nOl = l // n
        mOl = l // m
        sinX = np.array([i * nOl + 1 for i in range(n)])
        tinX = np.array([i * mOl + 1 for i in range(m)])
        matchList = list(set(sinX) & set(tinX))
        
        if len(matchList) == 0:
            continue

        scX = [np.where(sinX == commonIndex)[0][0] for commonIndex in matchList]
        tcX = [np.where(tinX == commonIndex)[0][0] for commonIndex in matchList]

        # import ipdb; ipdb.set_trace()

        if [s[sMatch] for sMatch in scX] == [t[tMatch] for tMatch in tcX]:
            check = False
            matchFlag = True
        
        if iter == min(len(s), len(t)):
            check = False
            matchFlag = False

        iter += 1

    if matchFlag:
        print(l)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
l = n * m // gcd(n, m)
a = ["" for i in range(l)]
for i in range(n):
    a[i*l//n] = s[i]
for i in range(m):
    if a[i*l//m] != "":
        if a[i*l//m] == t[i]:
            continue
        else:
            print(-1)
            exit()
    else:
        continue
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):
            hoge = (i-1)*k/N+1
            fuga = (j-1)*k/M+1
            if(hoge < fuga):
                break
            elif(hoge == fuga):
                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:

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

nsky = n
msky = m
while not nsky % msky == 0:
    tmp = msky
    msky = nsky % msky
    nsky = tmp
skys = msky

idx_n = 1
idx_m = 1
idx_x = 0
okans = -1
skbs = 0

while n * idx_n < 10000000000 and m * idx_m < 10000000000 and okans < 0:
    if n * idx_n == m * idx_m:
        idx_2 = 0
        
        while (n/skys)*idx_2 < n:
            if s[int(n/skys)*idx_2] == t[int(m/skys)*idx_2]:
                if (n/skys)*(idx_2+1) == n:
                    okans = n * idx_n
                idx_2 = idx_2 + 1
            else:
                idx_2 = n
                
        if skbs == 0:
            skbs = idx_n

        idx_x = idx_x + 1
        idx_m = skbs * idx_x
        idx_n = skbs * idx_x
    elif n * idx_n > m * idx_m:
        idx_m = idx_m + 1
    elif n * idx_n < m * idx_m:
        idx_n = idx_n + 1

print(okans)

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
    c = a % b
    return gcd(b, c)
 
def lcm(x, y):
    return (x * y) // gcd(x, y)

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
ans = 0
fans = ans

_lcm = lcm(len(S), len(T))
for k in list(reversed(range(1, (len(S) * len(T))//_lcm + 1))):
    ans = k * _lcm
    s = [(i * ans)//len(S) + 1 for i in range(len(S))]
    t = [(i * ans)//len(T) + 1 for i in range(len(T))]
    pool = s + t
    double_st = []
    
    for i in range(len(S)):
        if (len(T)*i)%len(S) == 0 and (len(T) * i)//len(S) <len(T):
            double_st += [(i * ans)//len(S) + 1]
    isImpossible = False

    for st in double_st:
        s_i = ((st-1) * len(S))//ans
        t_i = ((st-1) * len(T))//ans
        if s_i == -1 or t_i == -1:
            continue
        if S[s_i] != T[t_i]:
            isImpossible = True
            break

            
    if isImpossible:
        break
    else:
        success = True
        fans = ans

if not success:
    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
    c = a % b
    return gcd(b, c)
 
def lcm(x, y):
    return (x * y) // gcd(x, y)

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
ans = 0
fans = ans

_lcm = lcm(len(S), len(T))
for k in list(reversed(range(1, (len(S) * len(T))//_lcm + 1))):
    ans = k * _lcm
    s = [(i * ans)//len(S) + 1 for i in range(len(S))]
    t = [(i * ans)//len(T) + 1 for i in range(len(T))]
    pool = s + t
    double_st = []
    
    for i in range(len(S)):
        if (len(T)*i)%len(S) == 0 and (len(T) * i)//len(S) <len(T):
            double_st += [(i * ans)//len(S) + 1]
    isImpossible = False

    for st in double_st:
        s_i = my_index(s, st, -1)
        t_i = my_index(t, st, -1)
        if s_i == -1 or t_i == -1:
            continue
        if S[s_i] != T[t_i]:
            isImpossible = True
            break

            
    if isImpossible:
        break
    else:
        success = True
        fans = ans

if not success:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
 
n, m = (int(i) for i in input().split()) 
 
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))
 
ind_list = []
for i in range(m):
    if n_ind.count((lcm / m) * (i)) == 1:
        ind_list.append((lcm / m) * (i))
 
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:
from fractions import gcd
N,M = map(int,input().split())
S,T = [input() for i in range(2)]
for i in range(N):
  for j in range(M):
    if i*M == j*N and S[i] != T[j]:
        print(-1)
        exit()
    elif i == N-1 and j == M-1:
      print(int(N*M/gcd(N,M)))

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

def lcm(a, b):
	return a * b // fractions.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 = 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(x, y):
    return (x * y) // gcd(x, y)

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
ans = 0

_lcm = lcm(len(S), len(T))
for k in range(1, (len(S) * len(T))//_lcm + 1):
    ans = k * _lcm
    s = [(i * ans)//len(S) + 1 for i in range(len(S))]
    t = [(i * ans)//len(T) + 1 for i in range(len(T))]
    pool = s + t

    double_st = []
    
    for i in range(len(S)):
        if (len(T)*i)%len(S) == 0 and (len(T) * i)//len(S) <len(T):
            double_st += [(i * ans)//len(S) + 1]
    isImpossible = False

    for st in double_st:
        s_i = my_index(s, st, -1)
        t_i = my_index(t, st, -1)
        if s_i == -1 or t_i == -1:
            continue
        if S[s_i] != T[t_i]:
            isImpossible = True
            break

            
    if not isImpossible:
        success = True
        break

if not success:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N,M = map(int,input().split())
S,T = [input() for i in range(2)]
for i in range(1,N+1):
  for j in range(1,M+1):
    if (i-1)*M == (j-1)*N and S[i-1] != T[j-1]:
        print(-1)
        exit()
    elif i == N and j == M:
      print(int(N*M/gcd(N,M)))

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 = 9999
#M = 9999
#S = 'acp'
#T = 'ae'

if N * M > 10000000000:
    print(-1)
    sys.exit()

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)

#print(Xn_list)

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

#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:
# 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 = max(n, m)
nl = nl_max 
while nl < 10 ** 10:
	if nl % m:
		nl += nl_max
		continue

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

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

ind_list = []
for i in range(m):
    if n_ind.count((lcm / m) * (i)) == 1:
        ind_list.append((lcm / m) * (i))

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:
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)]
f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N-1:
            break
        if t > M -1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break


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( (L // match)-1 ,0,-1):
            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 sys
n,m=map(int,input().split())
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=(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:
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 not(x_idx == zzz or 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:
        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 my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
ans = 0

_lcm = lcm(N, M)
for k in range(1, N*M//_lcm + 1):
    ans = k * _lcm
    s = [(i * ans)//N + 1 for i in range(len(S))]
    t = [(i * ans)//M + 1 for i in range(len(T))]

    pool = s + t

    double_st = [x for x in set(pool) if pool.count(x) > 1]
    isImpossible = False

    for st in double_st:
        s_i = my_index(s, st, -1)
        t_i = my_index(t, st, -1)
        if s_i == -1 or t_i == -1:
            continue
        if S[s_i] != T[t_i]:
            isImpossible = True
            break
            
    if not isImpossible:
        success = True
        break

if not success:
    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

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)
lN = lcm_num // N
lM = lcm_num // M

for i in range(lcm_num):
    if i == 0 or (i%(lN) == 0 and i%(lM) == 0):
        if S[i//lN] == T[i//lM]:
            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
 
X = N*M // gcd(N,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N * M:
    print(X)
else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        m = gcd(  L // N,  L // M)
        for j in range(1, (N*M*m//L) ):
            if S[j * L // M // m] != T[ j * L // N // m ]:
                L = -1
                break
        if L == X * i:
            break
    print(L)

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
    c = a % b
    return gcd(b, c)
 
def lcm(x, y):
    return (x * y) // gcd(x, y)

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
ans = 0

_lcm = lcm(N, M)
for k in range(1, N*M//_lcm + 1):
    ans = k * _lcm
    s = [(i * ans)//N + 1 for i in range(len(S))]
    t = [(i * ans)//M + 1 for i in range(len(T))]

    pool = s + t

    double_st = [x for x in set(pool) if pool.count(x) > 1]
    isImpossible = False

    for st in double_st:
        s_i = my_index(s, st, -1)
        t_i = my_index(t, st, -1)
        if s_i == -1 or t_i == -1 or s_i >= len(S) or t_i >= len(T):
            continue
        if S[s_i] != T[t_i]:
            isImpossible = True
            
    if not isImpossible:
        success = True
        break

if not success:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
a = list(map(int,input().split()))
n = a[0]
m = a[1]
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(x, y):
    return (x * y) // gcd(x, y)
l = lcm(n,m)
lists = []
listt = []
for i in range(n):
    if n == 0:
        lists.append(1)
    else:
        lists.append(1+i*(l//n))
for i in range(m):
    if m == 0:
        listt.append(1)
    else:
        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: 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)
lN = lcm_num // N
lM = lcm_num // M

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

print(lcm_num)

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))
si = ti= 0
ss = tt = 1
for i in range(l):
    if ss<i:
        ss=int(ss+l/n)
        si+=1
    if tt<i:
        tt=int(tt+l/m)
        ti+=1
    if ss<=l and tt<=l and i<=ss and i<=tt and ss==tt:
        if s[si]!=t[ti]:
            print('-1')
            break
else:
    print(l)