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: Accepted

Solution code:
import fractions as f
n,m=map(int,input().split());g=f.gcd(n,m);print(-1if input()[::n//g]!=input()[::m//g]else n*m//g)

Submission status: Accepted

Solution code:
import sys
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

# N < M
def gcd(N,M):
    if(N > M):
        tmp = N
        N = M
        M = tmp
    r = M % N
    while(r != 0):
        M = N
        N = r
        r = M%N
    return N

def lcm(N,M):
    return(N*M/gcd(N,M))

if (N % M == 0):
    if S == T:
        print(M)
    else:
        p = int(N/M)
        for i in range(M):
            if T[i] != S[i*p]:
                print(-1)
                sys.exit()
        print(N)
elif (M % N == 0):
    if S == T:
        print(M)
    else:
        p = int(M/N)
        for i in range(N):
            if S[i] != T[i*p]:
                print(-1)
                sys.exit()
        print(M)
else:
    mngcd = gcd(N,M)
    k = int(N/mngcd)
    m = int(M/mngcd)
    for i in range(mngcd):
        if S[i*k] != T[i*m]:
            print(-1)
            sys.exit()
    print(int(lcm(N,M)))

Submission status: Accepted

Solution code:
import fractions as fr

N,M=[int(i) for i in input().split()]
S=input()
T=input()
Slist=list(S)
Tlist=list(T)
ans=0
GCD=0

if M==N:
    if S==T:
        ans=len(S)
    else:
        ans=-1
else:
    GCD=fr.gcd(N,M)
    if GCD==1:
        if Slist[0]==Tlist[0]:
            ans=int(N*M/GCD)
        else:
            ans=-1
    else:
        LCM=int(N*M/GCD)
        a=int(LCM/N)
        b=int(LCM/M)
        LCM2=int(a*b/fr.gcd(a,b))
        f=0
        for i in range(int(LCM/LCM2)):
            if Slist[i*b]!=Tlist[i*a]:
                f+=1
                break
        if f==0:
            ans=LCM
        else:
            ans=-1
print(ans)

Submission status: Accepted

Solution code:
def a_two_abbreviations(N, M, S, T):
    from fractions import gcd

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

    # LはLCM(N,M)の倍数でなければならない
    # (1): jL/N=kL/M を満たすすべての非負整数(j,k)の組についてS[j]==T[k]か
    # 調べるので、Lを整数倍したところで(j,k)の組は変わらない。よってL=lcm(N,M)
    L = lcm(N, M)

    # ab = gcd(a,b)*lcm(a,b) の関係から、下のようにn, mを定義すれば、
    # jm = kn を満たすすべての(j,k)の組についてS[j]==T[k]であればいい。
    # (1)式だと分母が異なるが、この変換を行うと、分母が等しくなるし、
    # M=Gm, N=Gnであり、M, Nの共通する素因数はGが「引き受ける」ため、
    # m, nは互いに素になって扱いやすい
    G = gcd(N, M)
    n, m = N // G, M // G

    ans = L
    # M=gm, N=gnとなるため、pが下の範囲の場合について調べる
    for p in range(gcd(N, M)):
        a, b = p * n, p * m
        if S[a] != T[b]:
            ans = -1
            break

    return ans

N, M = [int(i) for i in input().split()]
S = input()
T = input()
print(a_two_abbreviations(N, M, S, T))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#-*- coding: utf-8 -*-

from collections import defaultdict
from math import factorial as f
from fractions import gcd as g

n, m = [int (i) for i in raw_input ().split ()]
s = raw_input ()
t = raw_input ()
L = n * m / g (n, m)
d = defaultdict (str)
cnt = 0
ok = True
for i in range (n):
    d [i * L / n] = s [i]
for i in range (m):
    ok &= (d [i * L / m] == '' or d [i * L / m] == t [i])
    d [i * L / m] = t [i]
if not ok: L = -1
print L

Submission status: Accepted

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


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


N, M = map(int, input().split())
s = input()
t = input()

g = gcd(N, M)
n, m = N // g, M // g

L = lcm(N, M)

k = 0
flg = True
while k * n * m < L:
    if s[k * n] != t[k * m]:
        flg = False
        break
    k += 1

print(L if flg else -1)

'''
0-indexed -> 1-indexed
a * L/N == b * L/M
となるすべてのa, bについて
s[a] == t[b]が必要

a * M == b * N
a * gcd(N, M) * m == b * gcd(N, M) * n
a * m == b * n
m, nは互いに素

a = k * n
b = k * m
k: 0以上の整数
とおける

文字列Xの長さLは, lcm(N, M)の倍数だが
調べるa, bの組は, Lの値によらないので
構成できるときは
L = lcm(N, M)とするのが最小
'''

Submission status: Accepted

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

n,m=map(int,input().split())
s=input()
t=input()
c=0
g=gcd(n,m)
x=n*m//(gcd(n,m))
for k in range(g):
    if s[int(k*n/g)]==t[int(k*m/g)]:
        continue
    else:
        c=-1
        break
       
if c==-1:
    print(c)            
                        
else:
    print(x)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)

n,m=map(int,input().split())
s=input();t=input()
c=0
l=lcm(n,m)
a=l//n;b=l//m

for i in range(n):
  if (i*a)%b==0:
    if s[i]==t[i*a//b]:c+=1
    else:
      break
if c==(l//lcm(a,b)):print(l)
else:print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)

n,m=map(int,input().split())
s=input()
t=input()
c=0
a=lcm(n,m)//n
b=lcm(n,m)//m

for i in range(n):
  if (i*a)%b==0:
    if s[i]==t[int(i*a/b)]:c+=1
    else:
      break
if c==(int(lcm(n,m)/lcm(a,b))):print(lcm(n,m))
else:print(-1)

Submission status: Accepted

Solution code:

iN ,iM = [int(_) for _ in input().split()]
sS = input().rstrip()
sT = input().rstrip()

def fgcd(a,b):
    if b :
        return fgcd(b,a%b)
    else:
        return a

iD = fgcd(iN,iM)

if sS[0::iN//iD] == sT[0::iM//iD]:
    print(iN*iM//iD)
else:
    print("-1")

Submission status: Accepted

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


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


n, m = map(int, input().split())
s = input()
t = input()
GCD = gcd(n, m)
n_ = n // GCD
m_ = m // GCD

ans = lcm(n, m)
for i in range(GCD):
    if s[i * n_] != t[i * m_]:
        ans = -1
        break
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(a,b): 
    return int(abs(a * b) / gcd(a,b) if a and b else 0)

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

g = gcd(N,M)
n = N // g
m = M // g

for k in range(g):
    if S[k * n] != T[k * m]:
        print(-1)
        quit()
print(lcm(N,M))

Submission status: Accepted

Solution code:
import fractions


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

# 先頭文字が一致しない場合はよい文字列は存在しないので終了
if s[0] != t[0]:
    print(-1)
    exit()

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

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

# 共通部分を取得
same = list(ss & tt)

# メモリ開放
del ss
del tt

a = [s[item // (l // n)] for item in same]
b = [t[item // (l // m)] for item in same]

print(l) if a == b else print(-1)

Submission status: Accepted

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


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


dic1, dic2 = {}, {}
for i in range(N):
    dic1[(L // N) * i + 1] = S[i]

for j in range(M):
    dic2[(L // M) * j + 1] = T[j]

num = L // gcd(N, M)
if dic1[1] != dic2[1]:
    num = -1
for k, v in dic1.items():
    if k in dic2:
        if dic2[k] != v:
            num = -1

print(num)

Submission status: Accepted

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

Submission status: Accepted

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()
g = gcd(N,M)
l = N*M//g

n = N//g
m = M//g

ans = l

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

Submission status: Accepted

Solution code:
from fractions import gcd

def solve(N, M, S, T):
    d = gcd(N, M)
    n = N // d
    m = M // d
    
    for i in range(d):
        if S[n*i] != T[m*i]:
            return -1
    return n * m * d
	

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

Submission status: Accepted

Solution code:
def gcd(a, b):  
  if b == 0: return a
  return gcd(b, a % b)
n, m =  map(int, input().split())
g = gcd(n, m)
l = n * m // g
n = n//g
m = m//g
s = list(str(input()))[::int(n)]
t = list(str(input()))[::int(m)]
if s == t:
  print(l)
else:
  print("-1")

Submission status: Accepted

Solution code:
from fractions import gcd
 
 
def solve(n, m, s, t):
    g = gcd(n, m)
    ng = n // g
    mg = m // g
 
    for h in range(g):
        if s[ng * h] != t[mg * h]:
            return -1
    return ng * mg * g
 
 
n, m = list(map(int, input().split()))
s = input()
t = input()
print(solve(n, m, s, t))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

Submission status: Accepted

Solution code:
import math

N, M = list(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)

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

d = dict()

for i in range(N):
    index = 1 + (L // N) * i
    d[index] = S[i]

for j in range(M):
    index = (1 + (L // M) * j)
    if index in d:
        if d[index] != T[j]:
            print(-1)
            exit()
print(L)

Submission status: Accepted

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

    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)

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: Accepted

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)

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


L = lcm(N, M)

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: Accepted

Solution code:
import fractions
n,m = map(int, input().split(' '))
s = input()
t = input()
g = fractions.gcd(n, m)
Flag = True
for i in range(n):
    if (m*i)%n == 0:
        if s[i] != t[int((i*m)/n)]:
            Flag = False
if Flag:
    print(int((n*m)/g))
else:
    print('-1')

Submission status: Accepted

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

Slist=list(S)
Tlist=list(T)

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

A=int(N/G)
B=int(M/G)

for i in range(G):
    if Slist[i*A]!=Tlist[i*B]:
        ans=-1
        break
    else:
        ans=L
print(ans)

Submission status: Accepted

Solution code:
import platform
ver = platform.python_version_tuple()
if int(ver[1]) < 5:
    from fractions import gcd
else:
    from math import gcd

from sys import stdin
from bisect import bisect

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

    L = lcm(N, M)
    s = [i * (L // N) + 1 for i in range(N)]
    t = [i * (L // M) + 1 for i in range(M)]
    for i, x in enumerate(s):
        n = bisect(t, x)
        if t[n-1] == x:
            if T[n-1] != S[i]:
                print(-1)
                return
    print(L)

input = lambda: stdin.readline().rstrip()
lcm = lambda x, y: x * y // gcd(x, y)
main()

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x,y):
    return (x*y)//gcd(x,y)
n,m=map(int,input().split())
s=input()
t=input()
d=lcm(n,m)
p=d//n
q=d//m
h=lcm(p,q)
l=d//h
for i in range(0,l):
    g=i*h
    if s[g//p]!=t[g//q]:
        print(-1)
        break
else:
    print(d)

Submission status: Accepted

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
gcd_num = lN * lM

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

print(lcm_num)

Submission status: Accepted

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
    starti = 0
    startj = 0
    for i in range(starti, N):
        for j in range(startj, M):
            hoge = i*k/N+1
            fuga = j*k/M+1
            if(hoge < fuga):
                startj = j - 1
                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: Accepted

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
fans = 0

_lcm = lcm(len(S), len(T))

def isImpble(k, _lcm):
    global success
    global S
    global T
    global fans
    
    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:
        return True
    else:
        success = True
        fans = k*_lcm
        return False
        

imp = isImpble((len(S) * len(T))//_lcm, _lcm)

if not imp:
    for k in range(1, (len(S) * len(T))//_lcm ):
        imp = isImpble(k, _lcm)
        if success:
            break
    

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

Submission status: Accepted

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

x=1

gcd=fractions.gcd(M,N)

if gcd==0:
  print(-1)
  sys.exit()

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

lst=[S[0]]


lcm=(M*N)//gcd
dn=lcm//N
dm=lcm//M

dlcm=(dn*dm)//fractions.gcd(dn,dm)

for i in range(lcm//dlcm):
  if S[dlcm*i//dn] != T[dlcm*i//dm]:
    print(-1)
    sys.exit()
print(lcm)

Submission status: Accepted

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

def lcm(a,b):
  return int(a*b/gcd(a,b))
 
N,M = map(int,input().split())
S = input()
T = input()
L = lcm(N,M)
flag = True
min_len = min(N,M)
s_index = int(int(L/M)/gcd(int(L/M),int(L/N)))
t_index = int(int(L/N)/gcd(int(L/M),int(L/N)))

if N == M:
  for i in range(N):
    if S[i] == T[i]:
      continue
    else:
      flag = False
      break
else:
  for i in range(min_len):
    if i * s_index < N-1 and i*t_index < M - 1:
      if S[i*s_index] == T[i*t_index]:
        continue
      else:
        flag = False
        break
    else:
      break
    
if flag:  
  print(L)
else:
  print(-1)

Submission status: Accepted

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):
        if n_s * m_s < j:
            return -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: Accepted

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)

width = fractions.gcd(N, M)

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

print(ans)

Submission status: Accepted

Solution code:

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

cnt = 1
ns = 1
nt = 1
ss = 0
tt = 0
fail = False


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


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

while l <= n * m:
    fail = False
    while not(ns > l or nt > l):
        while not(ns <= nt):
            nt += l / m
            tt += 1

        if(ns == nt) and (s[ss] != t[tt]):
            fail = True
            break

        ns += l / n
        ss += 1
    if not(fail):
        break
    cnt += 1
    l = ll * cnt

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

Submission status: Accepted

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 = N*M // gcd(N,M)

n = L // N
m = L // M

list_n = [i for i in range(0,L,n)]
list_m = [i for i in range(0,L,m)]

list_common = sorted(list(set(list_n) & set(list_m)))

for i in list_common:
    if i == 0:
        if S[0] != T[0]:
            print('-1')
            exit()
    elif S[i//n] != T[i//m]:
        print('-1')
        exit()

print(L)

Submission status: Accepted

Solution code:
import fractions
 
N, M = [int(i) for i in raw_input().split(" ")]
S = raw_input()
T = raw_input()
 
def solve():
    gcd = fractions.gcd(N, M)
    for i in range(1, gcd + 1):
        if S[-int(N / gcd) * i] != T[-int(M / gcd) * i]:
            return -1
    return int(N * M / gcd)
 
print(solve())

Submission status: Accepted

Solution code:
from fractions import *

def lcm(a,b): 
    return int(abs(a * b) / gcd(a,b) if a and b else 0)

def getDivisors(a,b):
    divisors = []
    for i in range(2,min(a,b)+1):
        if a % i == 0 and b % i == 0:
            divisors.append(i)
    return divisors

N,M = map(int,input().split())
a = input()
b = input()

if a[0] != b[0]:
    print(-1)
elif gcd(N,M) == 1:
    print(lcm(N,M))
elif N != M:
    divisors = getDivisors(N,M)

    for i in divisors:
        k = N//i
        l = M//i
        while k < N and l < M:
            if a[k] != b[l]:
                print(-1)
                quit()
            k += N//i
            l += M//i
    print(lcm(N,M))
else:
    if a == b: print(N)
    else: print(-1)

Submission status: Accepted

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)
y = int(N*M/x)

for i in range(x):
    if S[int(i*y/M)] == T[int(i*y/N)]:
        continue
    else:
        print(-1)
        exit()
print(y)

Submission status: Accepted

Solution code:
import functools, fractions

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

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

def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res

def check2(x, L, NM):
    return int((x-1)*NM/L)

L = lcm(N,M)
ans = L


a = list(set(check(L, N)) & set(check(L, M)))
for i in a:
    if S[check2(i, L, N)] != T[check2(i, L, M)]:
        ans = -1
        break
print(ans)

Submission status: Accepted

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

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

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

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

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


LCM=lcm(N,M)

if gcd(N,M)==1:
	print N*M
else:
	n=N/gcd(N,M)
	m=M/gcd(N,M)
	S_tmp=""
	T_tmp=""

	for i in range(N/n): S_tmp+=S[ i*n ]
	for i in range(M/m): T_tmp+=T[ i*m ]

	if S_tmp==T_tmp:
		print LCM
	else:
		print -1

Submission status: Accepted

Solution code:

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    S = buf
    buf = input()
    T = buf
    L = lcm(N, M)
    # main part
    i = 0
    j = 0
    while i < len(S) and j < len(T):
        if i * (L / N) == j * (L / M):
            if not S[i] == T[j]:
                print(-1) # faliure
                return
            else:
                i += 1
                j += 1
        elif i * (L / N) < j * (L / M):
            i += 1
        elif i * (L / N) > j * (L / M):
            j += 1
    print(L) # success
    return

# 最大公約数 & 最小公倍数
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return int(a)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions


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

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

span = fractions.gcd(n, m)
for i in range(span):
    if s[int(n/span)*i] != t[int(m/span)*i]:
        print("-1")
        exit()
print(lcm(n, m))

Submission status: Accepted

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)

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

MA = [S[0]]
NA = [T[0]]

L = lcm(M, N)

m = L/M
n = L/N

for i in range(M):
   if i % n == 0:
       MA.append(S[i])

for i in range(N):
   if i % m == 0:
       NA.append(T[i])

if MA == NA:
   print(L)
else:
   print("-1")

Submission status: Accepted

Solution code:
import sys


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

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

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

l=lcm(n[0],n[1])
p=lcm(l//n[0],l//n[1])


i=0
a=p//(l//n[0])
b=p//(l//n[1])
k=min(n[0],n[1])
while (i*a<n[0]) and (i*b<n[1]) :
    if s[i*a]!=t[i*b]:
        print("-1")
        sys.exit()
    i += 1
    
print(l)

Submission status: Accepted

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]


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

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


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

print(ret)

Submission status: Accepted

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


N,M = [int(i) for i in input().split()]

S = input()
T = input()

x = N * M // gcd(N,M)
flag = True

#print(S[0 * (N / math.gcd(N,M)) + 1])
for i in range(gcd(N,M)):
  if not(S[i * (N //gcd(N,M))] == T[i * (M // gcd(N,M))]):
    flag = False
#    print(S[i * (N // math.gcd(N,M))]  , T[i * (M // math.gcd(N,M))])
if flag:
  print(x)
else:
  print('-1')

Submission status: Accepted

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:
        L = X
        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 :
            print(L)
        else:
            print(-1)

Submission status: Accepted

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

L = N * M
n, m = N, M
if n < m:
    n, m = m, n
while m != 0:
    n, m = m, n%m
GCD = n
LCM = L//n

if GCD == 1 and S[0] == T[0]:
    print(L)
elif S[::N//GCD] == T[::M//GCD]:
    print(LCM)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
x = fractions.gcd(N,M)
a = []
b = []
for i in range(int(x)):
  a.append(S[int(i*N/x)])
for i in range(int(x)):
  b.append(T[int(i*M/x)])
if a==b:
  print (int(N*M/x))
else:
  print (-1)

Submission status: Accepted

Solution code:
import bisect

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

ind = 0
ind_max = j-1

for i,v in enumerate(SS):
    ind = bisect.bisect_left(TT, v,ind, j)
    if ind == j:
        break
#    print(ind)
    if TT[ind] == v:
        if S[i] == T[ind]:
            continue
        else:
            print(-1)
            exit()
print(lcm)

Submission status: Accepted

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

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

def enstr(A,g):
    m=''
    for i in range(len(A)//g):
        m+=A[g*i]
    return m
    
if S[0]==T[0]:
    gcd=gcd(N,M)
    n,m=N//gcd,M//gcd
    s,t=enstr(S,n),enstr(T,m)
    if s==t:
        print(N*M//gcd)
    else:
        print(-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

def gcd(n,m):
    if m==0:
        return n
    else:
        return gcd(m,n%m)

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

x=gcd(n,m)

if x==n:
    for i in range(0,m+1,n):
        if t[i]!=s[i//n]:
            print(-1)
            sys.exit()
    print(n*m//x)
elif x==m:
    for i in range(0,n+1,m):
        if s[i]!=t[i//m]:
            print(-1)
            sys.exit()
    print(n*m//x)
elif x!=1:
    i=0
    j=0
    while i<n and j<m:
        if s[i]!=t[j]:
            print(-1)
            sys.exit()
        else:
            i+=(n//x)
            j+=(m//x)
    print(n*m//x)
else:
    if s[0]!=t[0]:
        print(-1)
        sys.exit()
    print(n*m)

Submission status: Accepted

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()
g = gcd(n,m)
l = n*m//g
s1 = n/g
t1 = m/g
x = []
y = []
for i in range(len(s)):
  if i % s1 == 0:
    x.append(s[i])  
for i in range(len(t)):
  if i % t1 == 0:
    y.append(t[i])  
print(l) if x==y else print(-1)

Submission status: Accepted

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
result = ll
for i in xrange(n):
    if not (i*m) % n :
            tmp=i*m/n
            if s[i] != t[tmp] :
                result= -1
print result

Submission status: Accepted

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)
nn = ans//n
mm = ans//m
e = lcm(nn,mm)
for i in range(1,ans,e):
    # print(i // (ans//n),i // (ans//m))
    # print(s[i // (ans//n)],t[i // (ans//m)])
    if s[i // (ans//n)] != t[i // (ans//m)]:
        print(-1)
        exit()
print(ans)