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:
N, M = map(int, input().split())
S = input()
T = input()
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
def lcm(a, b):
    return a * b // gcd(a, b)
l = lcm(N, M) 
print(lcm(N, M)) if all(S[(l//M) * i] == T[(l//N) * i] for i in range(gcd(N, M))) else print(-1)

Submission status: Accepted

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
g = fractions.gcd(N, M)
n = N // g
m = M // g
out = n * m * g
for k in range(g):
  if S[k * n] != T[k * m]:
    out = -1
    break
print(out)

Submission status: Accepted

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

# 15, 9
# 3$BJ8;z$:$D8+$F$$$/!"(B5$BJ8;z$:$D8+$F$$$/(B
LEN = N*M // gcd(N,M) # 45
p = LEN // N # 3
q = LEN // M # 5
lcm = p*q//gcd(p,q)

for i in range(0, LEN//lcm):
    if S[i*q] != T[i*p]:
        print(-1)
        exit()
print(LEN)

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()
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
k = gcd(max(N,M),min(N,M))
lcm = N*M // gcd(max(N,M),min(N,M))
n = N//k
m = M//k
for i in range(k):
    if not s[n*i]==t[m*i]:
        print(-1)
        exit()
print(lcm)

Submission status: Accepted

Solution code:
def main28():
    import sys
    N, M = (int(x) for x in input().split())

    if N >= M:
        S = input()
        T = input()
    else:
        T = input()
        S = input()

    def lcm(n, m):
        gcd = 0
        for i in range(1, min(n, m) + 1):
            if n % i == 0 and m % i == 0:
                gcd = i

        return int(n * m / gcd)

    LCM = lcm(N, M)

    a = int(LCM / max(N, M))
    b = int(LCM / min(N, M))

    for i in range(min(N, M)):
        small_index = i * b
        if int(small_index % a) == 0:
            if S[int(small_index / a)] != T[i]:
                print("-1")
                sys.exit()
    print(LCM)

main28()

Submission status: Accepted

Solution code:
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
  return gcd(b, a%b)

g = gcd(n, m)
l = n*m//g
nn = n//g
mm = m//g

for i in range(g):
  if s[i*nn] != t[i*mm]:
    print(-1)
    exit()
print(l)

Submission status: Accepted

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

#最大公約数
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

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

l=lcm(n,m)

a=l//n
b=l//m
ln=[]
lm=[]
i=0
while i<n:
    ln.append(i)
    i+=b
i=0
while i<m:
    lm.append(i)
    i+=a

p=0
for i in range(len(ln)):
    if s[ln[i]]!=t[lm[i]]:
        p=1
if p==0:
    print(l)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
x=gcd(n,m)
l=n*m//gcd(n,m)
for i in range(x):
    if s[i*(n//x)]!=t[i*(m//x)]:
        print(-1)
        exit()
print(l)

Submission status: Accepted

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

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

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


L = lcm(N, M)
X = {}


for i in range(0,N):
	X[i*L//N] = S[i]
# print(X)
for i in range(0,M):
	if X.get(i*L//M) != None:
		if X[i*L//M] != T[i]:
			print(-1)
			exit()
	else:
		pass
print(L)

Submission status: Accepted

Solution code:
def gcm(a, b) :
  while(b) :
    a, b = b, a%b
  return a
def lcm(a, b) :
  return int(a*b/gcm(a, b))

n, m = map(int, input().split())
s = list(str(input()))
t = list(str(input()))
s_out = []
t_out = []
for i in range(int(gcm(n, m))) :
  s_out.append(s[i*int(n/gcm(n, m))])
for i in range(int(gcm(n, m))) :
  t_out.append(t[i*int(m/gcm(n, m))])
  
if(s_out == t_out) : print(lcm(n, m))
else : print(-1)

Submission status: Accepted

Solution code:
def gcd(x,y):
  if y==0:
    return x
  return gcd(y, x%y)
def lcm(x,y):
  return x*y//gcd(x,y)
n,m=map(int,input().split())
ans=lcm(n,m)
s=list(input())
t=list(input())
p=n//gcd(n,m)
q=m//gcd(n,m)
flag=True
if p>=q:
  for i in range(0,m,q):
    if s[(p*i)//q]!=t[i]:
      flag=False
      break
else:
  for i in range(0,n,p):
    if s[i]!=t[(q*i)//p]:
      flag=False
      break
if flag:
  print(ans)
else:
  print(-1)

Submission status: Accepted

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

a, b = sorted([N, M])
while True:
	if b % a == 0:
		break
	else:
		a, b = b % a, a
GCM = abs(a)

LCM = int(N * M // GCM)
judge = "YES"
for i in range(GCM):
	if S[int(N // GCM) * i] != T[int(M // GCM) * i]:
		judge = "NO"
		print(-1)
		break
	else:
		pass

if judge == "YES":
	print(LCM)

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)


step = gcd(N, M)
step_N = N // step
step_M = M // step

if S[::step_N] == T[::step_M]:
    print(lcm(N, M))
else:
    print(-1)

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------------------
# Name:        module2
# Purpose:
#
# Author:      ysakamot
#
# Created:     15/12/2018
# Copyright:   (c) ysakamot 2018
# Licence:     <your licence>
#-------------------------------------------------------------------------------

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



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


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

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]

    L = lcm(N, M)
    input_raw = read_func().strip().split()
    S = input_raw[0]
    input_raw = read_func().strip().split()
    T = input_raw[0]



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

    print L





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcm(a,b):
    while b!=0:
        a,b=b,a%b
    return a

def solve():
    N,M=map(int,input().split())
    S=input()
    T=input()
    if (N == M) and (S == T):
        return N
    g=gcm(M,N)
    for i in range(g):
        #print(S[N//g*i], T[M//g*i])
        if S[N//g*i] != T[M//g*i]:
            break
    else:
        return M*N//g
    return -1

print(solve())

Submission status: Accepted

Solution code:
def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b
N,M=map(int,input().split())
S = input()
T = input()
g = gcd(M,N)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = input()
t = input()
#greatest common divisor/least common multiple
import fractions
gcd = int(fractions.gcd(n,m))
lcm = int(n*m/gcd)
counter=0
for i in range(gcd):
    if s[int(n/gcd)*i]!=t[int(m/gcd)*i]:
        print(-1)
        counter+=1
        exit()
if counter == 0:
    print(lcm)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
t = input()
def gcd(x, y):
    if y == 0: return x
    return gcd(y, x % y)
g = gcd(n, m)
for i in range(0, g):
    if s[i*n//g] != t[i*m//g]:
        print(-1)
        exit()
print(n*m//g)

Submission status: Accepted

Solution code:
from fractions import*
a,b=map(int,input().split())
c=gcd(a,b)
d=a*b//gcd(a,b)
s=input()
t=input()
for i in range(c):
    if s[i*(a//c)] != t[i*(b//c)]:
        print(-1)
        exit()
print(d)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
s=input()
t=input()
def euc(x,y):
  if max(x,y) % min(x,y)==0:
    return min(x,y)
  else:
    return euc(max(x,y) % min (x,y),min(x,y))
d=euc(n,m)
ans=n*int(m/d)
if d==1:
  if s[0]==t[0]:
    print(n*m)
  else:
    print(-1)
else:
  for i in range(d):
    if s[i*int(n/d)]!=t[i*int(m/d)]:
      ans=-1
  print(ans)

Submission status: Accepted

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

if __name__ == "__main__":
    n,m = map(int,input().split())
    s = input()
    t = input()
    G = gcd(n,m)
    ansL = n // G * m
    flag = True
    n = n // G
    m = m // G
    for i in range(0,G):
        if s[i*n] != t[i*m]:
            flag = False
    if flag:
        print(ansL)
    else:
        print(-1)

Submission status: Accepted

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

Submission status: Accepted

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

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


N_len_S, M_len_T = map(int, input().split())
S = input()
T = input()
g = gcd(N_len_S, M_len_T)
l = lcm(N_len_S, M_len_T)

ans = l
for k in range(g):
    # S[i]. T[j] : 文字列 X を構成したとき重なる文字。これらが等しければよい数字。
    i = N_len_S // g * k
    j = M_len_T // g * k
    if S[i] != T[j]:
        ans = -1
        break
print(ans)

Submission status: Accepted

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

from fractions import gcd
GCD = gcd(N, M)
LCD = N * M // GCD
A = N // GCD
B = M // GCD
for i in range(GCD):
    if S[A * i] != T[B * i]:
        print(-1)
        exit()
print(LCD)

Submission status: Accepted

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

import fractions

import sys
import math
import sys

input = sys.stdin.readline

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

##最小公倍数を求める
f = fractions.gcd(n, m)
f = n * m // f

nn = f//n
mm = f//m

##最小公倍数を求める
ff = fractions.gcd(nn, mm)
ff = nn * mm // ff
#print(nn,mm)
#print(f,ff)
for i in range(f//ff):
 #   print(i*mm,i*nn,s[i*mm],t[i*nn])
    if s[i*mm] != t[i*nn]:
        print(-1)
        quit()

print(f)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=list(input())
T=list(input())
L=gcd(N,M)
n=N//L
m=M//L
print(N*M//L if all([S[i*n]==T[i*m] for i in range(L)]) else "-1")

Submission status: Accepted

Solution code:
import fractions as math

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

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

    nmlcm = lcm(n,m)
    nn = nmlcm // n
    mm = nmlcm // m
    nnmmlcm = lcm(nn,mm)

    for i in range(nmlcm // nnmmlcm):
        #print(nnmmlcm*i)
        if s[nnmmlcm*i//nn] != t[nnmmlcm*i//mm]:
            print(-1)
            return
    print(nmlcm)

if __name__ == "__main__":
    main()

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 = list(input())
t = list(input())

for i in range(gcd(n, m)):
    if s[i * (n // gcd(n, m))] != t[i * (m // gcd(n, m))]:
        print(-1)
        break
    if i == gcd(n, m) - 1:
        print(lcm(n, m))

Submission status: Accepted

Solution code:
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)

n,m=map(int,input().split())
s,t=input(),input()
g,l=gcd(n,m),lcm(n,m)
for i in range(g):
    if s[(n//g)*i]!=t[(m//g)*i]:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

Solution code:
from sys import stderr
from fractions import gcd
from collections import defaultdict
def lcm(n,m): return n*m//gcd(n,m)
def func(i,l,n): return i*l//n + 1
N,M = map(int,input().split())
S = input()
T = input()
l = lcm(N,M)
dicS = defaultdict(int)
for i in range(0,len(S)):
    dicS[i+1] = func(i,l,N)
dicT = defaultdict(int)
for i in range(0,len(T)):
     dicT[func(i,l,M)] = i+1
print(dicS,file=stderr)
print(dicT,file=stderr)

flag = True
for i in range(1,N+1):
    if dicS[i] in dicT.keys():
        if S[i-1] != T[dicT[dicS[i]]-1]:
            flag = False
            break
if flag: print(l)
else: print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import defaultdict
def lcm(n,m): return n*m//gcd(n,m)
def func(i,l,n): return i*l//n + 1
N,M = map(int,input().split())
S = input()
T = input()
l = lcm(N,M)
dicS = defaultdict(int)
for i in range(1,len(S)):
    dicS[i+1] = func(i,l,N)
dicT = defaultdict(int)
for i in range(1,len(T)):
    dicT[func(i,l,M)] = i+1

flag = True
for i in range(1,N+1):
    if dicS[i] in dicT.keys():
        if S[i-1] != T[dicT[dicS[i]]-1]:
            flag = False
            break
if S[0] != T[0]: flag = False
if flag: print(l)
else: print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=(int(i) for i in input().split())
S=input()
T=input()
gcd_NM=gcd(N,M)
lcm_NM=(N*M//gcd_NM)
A=True
for i in range(gcd_NM):
  if S[(N//gcd_NM)*i]!=T[(M//gcd_NM)*i]:
    A=False 
    break
if A:
  print(lcm_NM)
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
import sys
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
def gcd(a,b):
    while b % a:
        a,b = b, a % b
    return a

N,M = IL()
s = S()
t = S()

agcd = gcd(N,M)
bgcd = N//agcd
lcm = N*M//agcd

for i in range(agcd):
    if s[i*lcm//M] == t[i*lcm//N]:
        continue
    else:
        print(-1)
        break
else:
    print(N*M//agcd)

Submission status: Accepted

Solution code:
def gcd(x, y):
  n = min(x, y)
  for i in range(n, 0, -1):
    if x % i == 0 and y % i == 0:
      return i

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


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

L = lcm(N, M)

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

print(L)

Submission status: Accepted

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


N, M = map(int, input().split())
S = input()
T = input()
G = int(gcd(N, M))
f = 0
for i in range(G):
    n, m = int(i * N / G), int(i * M / G)
    #print(n, m, S[n], T[m])
    if S[n] != T[m]:
        f = 1
        break

print(int(N * M / G) if f == 0 else -1)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int, input().split())
s = input()
t = input()

u = gcd(n,m)
l = n*m//u
x = n//u
y = m//u
for i in range(u):
    # print(n, m, u, l, i, i*x, s[i*x], i*y, t[i*y])
    if s[i * x] != t[i * y]:
        print(-1)
        break
else:
    print(l)

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=list(input())
t=list(input())
g=gcd(n,m)
a=n//g
b=m//g
judge=True
for i in range(g):
    if s[a*i]!=t[b*i]:
        judge=False
        break
print(g*a*b) if judge else print(-1)
#print(len(text))

Submission status: Accepted

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

n, m = [int(x) for x in input().split()]
s, t = [input() for _ in range(2)]

d = gcd(n, m)

nd = n // d
md = m // d

if all(s[nd*i] == t[md*i] for i in range(d)):
  print(n*m//d)
else:
  print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
from bisect import bisect_left
 
N, M = map(int, input().split())
S = input()
T = input()
 
if N > M:
    N, M = M, N
    S, T = T, S

G = N*M // gcd(N, M)
 
a = G//N
b = G//M
 
X = [a*i for i in range(N)]
Y = [b*j for j in range(M)]
 
for i, x in enumerate(X):
    j = bisect_left(Y, x)
    if j < M and Y[j] == x:
        if S[i] != T[j]:
            print(-1)
            break
else:
    print(G)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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


N, M = map(int, input().split())
if N >= M:
    s1 = input()
    s2 = input()
else:
    N, M = M, N
    s2 = input()
    s1 = input()


g = gcd(N, M)
lcm = N*M//g
ans = lcm
if N == M:
    if s1 == s2:
        ans = lcm
    else:
        ans = -1
else:
    if any(i != j for i, j in zip(s1[::N//g], s2[::M//g])):
        ans = -1
    else:
        ans = lcm
# else:
#    if s1[0] == s2[0]:
#        ans = lcm
#    else:
#        ans = -1
print(ans)

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)

def atwo(n,m,s,t):
    l=lcm(n,m)
    gc=gcd(n,m)
    if s[0::n//gc]==t[0::m//gc]:
        print(l)
        exit()
    else:
        print(-1)
        exit()

n,m=map(int,input().split())
print(atwo(n,m,input(),input()))

Submission status: Accepted

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

N,M = map(int,input().split())
S = input()
T = input()
ans = lcm_base(N,M)
for i in range(N):
    if M*i % N != 0:
        continue
    j = M*i // N
    if j >= M:
        continue
    if S[i] != T[j]:
        print(-1)
        exit()
print(ans)

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()
j = 0
a = gcd(n, m)
for i, c in enumerate(s):
	if i % (n // a) == 0:
		if c != t[(i // (n // a)) * (m // a)]:
			j = -1
			break
if j >= 0:
	j = lcm(n, m)
print(j)

Submission status: Accepted

Solution code:
from fractions import gcd

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

g = gcd(n,m)
a = n//g
b = m//g
flag = True
for i in range(g):
    if not s[a*i] == t[b*i]:
        flag = False
        break
if flag:
    print(g*a*b)
else:
    print(-1)

Submission status: Accepted

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

"""
参考：https://img.atcoder.jp/agc028/editorial.pdf
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

N, M = MAP()
S = input()
T = input()

lcm = lcm_base(N, M)
n = N // gcd(N, M)
m = M // gcd(N, M)
for i in range(gcd(N, M)):
    if S[i*n] != T[i*m]:
        print(-1)
        exit()
print(lcm)

Submission status: Accepted

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

N, M = MAP()
S = input()
T = input()

lcm = lcm_base(N, M)
# 何文字毎に文字が指定されるか
N_gap = lcm // N
M_gap = lcm // M
# 1文字ずつ全て確認することはない
for i in range(0, lcm, lcm//gcd(N, M)):
    # 文字の一致を確認する
    if S[i//N_gap] != T[i//M_gap]:
        print(-1)
        exit()
print(lcm)

Submission status: Accepted

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

N, M = MAP()
S = input()
T = input()

lcm = lcm_base(N, M)
N_gap = lcm // N
M_gap = lcm // M
for i in range(0, lcm, lcm//gcd(N, M)):
    if i % N_gap == 0 and i % M_gap == 0:
        if S[i//N_gap] != T[i//M_gap]:
            print(-1)
            exit()
print(lcm)

Submission status: Accepted

Solution code:
def gcd(x, y):
    if y == 0:
        return x
    if x < y:
        return gcd(y, x)
    return gcd(y, x % y)


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


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

g = gcd(N, M)
l = lcm(N, M)

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

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)

Submission status: Accepted

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

def gcd(n, m):
	if m < n:
		n, m = m, n
	while n:
		n, m = m%n, n
	return m

gcd_NM = gcd(N, M)
if S[::N//gcd_NM] == T[::M//gcd_NM]:
	print(N*M//gcd_NM)
else:
	print(-1)

Submission status: Accepted

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

def gcd(n, m):
	if m < n:
		n, m = m, n
	while n:
		n, m = m%n, n
	return m

gcd_NM = gcd(N, M)
if S[::N//gcd_NM] == T[::M//gcd_NM]:
	print(N*M//gcd_NM)
else:
	print(-1)

# large, small = sorted(N, M)
# if large%small == 0:
# 	if S[0] == T[0]:
# 		print(N*M)
# 	else:
# 		print(-1)
# else:
# 	large//small




gcd_NM = gcd(N, M)
M//gcd_NM, N//gcd_NM





################################
#-------------------------------
################################

# # no submit

# def gcd(n, m):
# 	if m < n:
# 		n, m = m, n
# 	while n:
# 		n, m = m%n, n
# 	return m
# def lcm(n, m):
# 	return n*m // gcd(n, m)

# n, m = map(int, input().split(" "))
# s, t = [input() for _ in range(2)]

# gcd_nm = gcd(n, m)
# print(lcm(n, m) if s[::n//gcd_nm] == t[::m//gcd_nm] else -1)

################################

# 6
# 2 3
# a__e__
# a_c_p_
# 最初の文字は同じ

# 6 3
# abcdef
# a_b_c_

# def gcd(n, m):
# 	if m < n:
# 		n, m = m, n
# 	while n:
# 		n, m = m%n, n
# 	return m
# def lcm(n, m):
# 	return n*m // gcd(n, m)

# n, m = map(int, input().split(" "))
# s, t = [input() for _ in range(2)]

# lcm_nm = lcm(n, m)
# s_ = "".join([s_i+"_"*(lcm_nm//n - 1) for s_i in s])
# t_ = "".join([t_i+"_"*(lcm_nm//m - 1) for t_i in t])
# for i in range(lcm_nm):
# 	if not (s_[i] in ["_", t_[i]] or t_[i] == "_"):
# 		print(-1)
# 		exit()
# print(lcm_nm)

Submission status: Accepted

Solution code:
import sys
def gcd(x, y):
  while y:
    x, y = y, x % y
  return x
n, m = map(int, input().split())
l = (n * m) // gcd(n, m)
a, b = l // n, l // m
s = input()
t = input()
i, j = 0, 0
while((i < n) & (j < m)):
  if (s[i] != t[j]):
    print(-1)
    sys.exit()
  else:
    i += b
    j += a
print(l)

Submission status: Accepted

Solution code:
import math
import sys

def gcd(x, y):
  while y:
    x, y = y, x % y
  return x
n, m = map(int, input().split())
l = (n * m) // gcd(n, m)
a = l // n
b = l // m
s = input()
t = input()
i = 0
j = 0
while((i < n) & (j < m)):
  if (s[i] != t[j]):
    print(-1)
    sys.exit()
  else:
    i += b
    j += a
print(l)

Submission status: Accepted

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

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

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

if S[:: n // gcd(n, m)] != T[:: m  // gcd(n, m)]:
    print(-1)
else:
    print(lcm(n, m))

Submission status: Accepted

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

# AGC028：A - Two Abbreviations
# import numpy as np
import fractions
def lcm(a,b): return abs(a * b) / fractions.gcd(a,b) if a and b else 0

def main():
    n, m = [int(i) for i in raw_input().strip().split(' ')]
    s = raw_input().strip()
    t = raw_input().strip()
    # l = np.lcm(n, m) # 45
    l = lcm(n, m) # 45
    n1 = l/n # 45/15 = 3
    m1 = l/m # 45/9 = 5
    # l1 = np.lcm(n1, m1) # lcm(3, 5) = 15
    l1 = lcm(n1, m1) # lcm(3, 5) = 15

    # d  n  s  u  s  r  a  y  u  k  u  a  i  i  a  
    # d    u    j    r    u    n    u    m    a    
    for i in range(l/l1):
        if s[i*m1] != t[i*n1]:
            print '-1'
            return
    print str(l)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b==0:
        return a
    else:
        return gcd(b, a%b)
N,M = map(int,input().split())
l = gcd(N,M)
S,T = input(),input()
OK = True
for i in range(l):
    ns = i*(N//l)
    nt = i*(M//l)
    if not S[ns]==T[nt]:
        OK = False
print((N*M)//l if OK else -1)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())

s = input()
t = input()

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

f = 1

for i in range(k):
    if not s[i*(a//k)]==t[i*(b//k)]:
        f = -1
        
if f<0:
    print(-1)
else:
    print(a*b//k)

Submission status: Accepted

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

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

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

if S[::l//m] == T[::l//n]:
    print(l)
else:
    print(-1)

Submission status: Accepted

Solution code:
import fractions

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

g = fractions.gcd(N, M)

lcm = N * M // g

ln = lcm // N
lm = lcm // M

count_n = 0
count_m = 0

while count_n != N and count_m != M:

    temp_n = count_n * ln
    temp_m = count_m * lm

    if temp_n == temp_m:
        if S[count_n] != T[count_m]:
            print(-1)
            break
    
    if count_n == (N - 1):
        count_m += 1
    elif count_m == (M - 1):
        count_n += 1
    elif temp_n <= temp_m:
        count_n += 1
    else:
        count_m += 1
else:
    print(lcm)

Submission status: Accepted

Solution code:
ls, lt = map(int, input().split())
s = list(input())
t = list(input())
def gcd(m,n):
    if n == 0:
        return m
    else:
        return gcd(n,m%n)
g = gcd(ls,lt)
m = ls // g
n = lt // g
ret = g*m*n
for i in range(g):
    if s[i*m] != t[i*n]:
        ret = -1
        break
print(ret)

Submission status: Accepted

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

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

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

l = lcm(n, m)
        
if S[::n // gcd(n, m)] == T[::m // gcd(n, m)]:
    print(l)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
n,m=N,M
s=input()
t=input()
while m:
  n,m=m,n%m
gcd=n
lcm=N*M//gcd
step1=N//gcd
step2=M//gcd
if all(s[i*step1]==t[i*step2] for i in range(gcd)):
  print(lcm)
else:
  print(-1)

Submission status: Accepted

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

n,m = map(int,input().split())
s = input()
t = input()
if n<m:
    tmp = m
    m = n
    n = tmp
    tmp = s
    s = t
    t = tmp
lcm = (n*m)//gcd(n,m)
ok = True
if s[0] != t[0]:
    ok = False

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

Submission status: Accepted

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

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
            

X=N*M/gcd(N,M)
double=[[(X/M)*i,(X/N)*i] for i in range(N*M/X)]
print X if all(S[d[0]]==T[d[1]] for d in double) else "-1"

Submission status: Accepted

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

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

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

if S[0::length//M] == T[0::length//N]:
    print(length)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M = map(int,input().split())
S = input()
T = input()
g = gcd(N,M)
ans = N*M//g
print(ans if S[::N//g] == T[::M//g] else -1)