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:
# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=list(input())
t=list(input())
lcd=(n*m)//gcd(n,m)
x=['' for _ in range(lcd)]

for i in range(max(n,m)):
    if i<n:
        a=i*(lcd//n)
        if x[a]==s[i] or x[a]=='':
            x[a]=s[i]
        else:
            print(-1)
            exit()
    if i<m:
        b=i*(lcd//m)
        if x[b]==t[i] or x[b]=='':
            x[b]=t[i]
        else:
            print(-1)
            exit()
        
print(lcd)

Submission status: Time Limit Exceeded

Solution code:
# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=list(input())
t=list(input())
lcd=(n*m)//gcd(n,m)
x=['' for _ in range(lcd)]

for i in range(n):
    a=i*(lcd//n)
    x[a]=s[i]

for i in range(m):
    b=i*(lcd//m)
    if x[b]==t[i] or x[b]=='':
        x[b]=t[i]
    else:
        print(-1)
        exit()
    
print(lcd)

Submission status: Time Limit Exceeded

Solution code:
from fractions import *
def lcm(x, y):
    return (x * y) // gcd(x, y)
N,M = map(int,input().split())
L = lcm(N,M)
words = [ "_" for i in range(L)]
S = str(input())
words[0] = S[0]
for i in range(1,N):
    num = (L // N) * i
    words[num] = S[i]
T = str(input())
if T[0] != S[0]:
    print(-1)
    exit()
for i in range(1,M):
    num = (L // M) * i
    if words[num] != "_":
        if T[i] != words[num]:
            print(-1)
            exit()
    else:
        words[num] = T[i]
print(L)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]+["end"]
TT=[j*t for j in range(M)]+["end"]
p,q=0,0
ans=N*s
for k in range(N*s):
    if SS[p]==k:
        if TT[q]==k:
            if S[p]!=T[q]:
                ans=-1
        p+=1
    if TT[q]==k:
        q+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]
TT=[j*t for j in range(M)]
p,q=0,0
ans=N*s
for k in range(N*s):
    if k in SS:
        if k in TT:
            if S[p]!=T[q]:
                ans=-1
        p+=1
    if k in TT:
        q+=1
print(ans)

Submission status: Time Limit Exceeded

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
 
def lcm(x, y):
    return int(x/gcd(x, y)*y)

lenx = lcm(N,M)

s_list = list(S)
t_list = list(T)

baisuu_s = lenx/N
baisuu_t = lenx/M
def check():
    for i in range(0,lenx):
        if i % baisuu_s==0 and i%baisuu_t == 0:
            if s_list[int(i/baisuu_s)] == t_list[int(i/baisuu_t)]:
                pass
            else:
                return False
    return True

if check():
    print(lenx)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import fractions

N, M = map(int, input().split())
S = input()
T = input()
size = N * M // fractions.gcd(N, M)

r = [0 for _ in range(size)]

ss = size // len(S)
for i, s in enumerate(S):
    r[i * ss] = s

ts = size // len(T)
ans = True
for i, t in enumerate(T):
    if not (r[i * ts] == t) | (r[i * ts] == 0):
        ans = False
        break
if ans:
    print(size)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

lcm = int(N * M / gcd(N, M))
nn = lcm // N
mm = lcm // M
flg = True

for i in range(lcm):
    if i % nn == 0 and i % mm == 0:
        if S[i//nn] == T[i//mm]:
            continue
        else:
            flg = False
if flg:
    print(lcm)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#E問題
N,M=map(int,input().split())
S=str(input())
Slist=list(S)
T=str(input())
Tlist=list(T)
#gcd(二つの数)
def gcd(GCD1,GCD2):
    x = min(GCD1,GCD2)
    y = max(GCD1,GCD2)
    if y%x == 0:
        return x
    else:
        return gcd(x,y%x)
MINA=int(N*M/gcd(N,M))
n=int(MINA/N)
m=int(MINA/M)
SS=["*" for i in range(MINA)]
TT=["*" for i in range(MINA)]
for i in range(N):
    SS[n*i]=Slist[i]
for i in range(M):
    TT[m*i]=Tlist[i]
flag=0
for i in range(MINA):
    if SS[i] == TT[i] or SS[i]=="*" or TT[i]=="*":
        pass
    else:
        flag=1
if flag==0:
    print(MINA)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

a = len(S)
b = len(T)

while (a % b != 0):
	c = a % b
	a = b
	b = c
 


boichung = len(S)*len(T)/b
Sn = boichung / len(S) 
Tm = boichung / len(T)


for i in range(len(S)):
    si = i*Sn + 1
    for j in range(len(T)):
        tj = j*Tm + 1
        if ((si == tj) & (S[i] != T[j])):
            boichung = -1 
            break
print(int(boichung))

Submission status: Time Limit Exceeded

Solution code:
#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = list(input())
T = list(input())
judge = 1 #1:可,0:不可

def gcd(a,b):
 while(b>0):
    a,b = b,a%b
 return a
def lcm(a,b):
 G = gcd(a,b)
 L = (a*b)//G
 return L

L = lcm(N,M)
ans = L
#metrial = [] #[Xの何番目の要素に使われるか,要素]
p,q = L//N,L//M
for i in range(L):
  if((i%p == 0)and(i%q == 0)): 
    if(S[i//p] != T[i//q]):
      ans = -1
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
flag = True
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)
L = lcm(N,M)
l = [-1 for i in range(L)]
for i in range(N):
    l[L//N*i] = ord(S[i])-97
for i in range(M):
    if l[L//M*i] == -1:
        l[L//M*i] = ord(T[i])-97
    elif l[L//M*i] == ord(T[i])-97:
        pass
    else:
        flag = False
if flag:
    print(L)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

g = fractions.gcd(N, M)
L = N * M // g

ss = L // N
ts = L // M
for i in range(L):
  if i % ss == 0 and i % ts == 0:
    if S[i//ss] != T[i//ts]:
      print(-1)
      sys.exit()
print(L)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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

#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(N, M)
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

#  print(XS, XT)
for i in range(0, L+1):
    if XS[i] != 'X' and XT[i] != 'X':
        if XT[i] != XS[i]:
            print(-1)
            exit()
print(L)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return int(a * b / gcd(a, b))


N, M = LI()
S = input()
T = input()
#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(len(S), len(T))
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

#  print(XS, XT)
for i in range(0, L+1):
    if XS[i] != 'X' and XT[i] != 'X':
        if XT[i] != XS[i]:
            print(-1)
            exit()
print(L)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return int(a * b / gcd(a, b))


N, M = LI()
S = input()
T = input()
#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(len(S), len(T))
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

#  print(XS, XT)
for i in range(0, L+1):
    if XS[i] != 'X' and XT[i] != 'X':
        if XT[i] != XS[i]:
            print(-1)
            exit()
print(L)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return int(a * b / gcd(a, b))


N, M = LI()
S = input()
T = input()
N, M = len(S), len(T)

X = lcm(len(S), len(T))
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
count = 0
while True:
    XS[int(count*L/N)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
while True:
    XT[int(count*L/M)] = T[count]
    count += 1
    if count > M-1:
        break

#  print(XS, XT)
for i in range(0, L+1):
    if XS[i] != 'X' and XT[i] != 'X':
        if XT[i] != XS[i]:
            print(-1)
            exit()
print(L)

Submission status: Time Limit Exceeded

Solution code:
from fractions import *
def lcm(x, y):
    return (x * y) // gcd(x, y)
N,M = map(int,input().split())
L = lcm(N,M)
words = [ "_" for i in range(L)]
S = str(input())
words[0] = S[0]
for i in range(1,N):
    num = (L // N) * i
    words[num] = S[i]
T = str(input())
if T[0] != S[0]:
    print(-1)
    exit()
for i in range(1,M):
    num = (L // M) * i
    if words[num] != "_":
        if T[i] != words[num]:
            print(-1)
            exit()
    else:
        words[num] = T[i]
print(L)

Submission status: Time Limit Exceeded

Solution code:
from fractions import *
def lcm(x, y):
    return (x * y) // gcd(x, y)
N,M = map(int,input().split())
L = lcm(N,M)
words = [[] for i in range(L)]
S = str(input())
words[0].append(S[0])
for i in range(1,N):
    num = (L // N) * i
    words[num].append(S[i])
T = str(input())
if T[0] != S[0]:
    print(-1)
    exit()
for i in range(1,M):
    num = (L // M) * i
    if len(words[num]) == 1:
        if [T[i]] != words[num]:
            print(-1)
            exit()
    else:
        words[num].append(T[i])
print(L)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
lcm_nm = int(n * m / gcd(n, m))
for i in range(lcm_nm):
  if(not(i % (lcm_nm/n) == 0 and i % (lcm_nm/m) == 0)):
    continue
  if(s[int(i / (lcm_nm/n))] != t[int(i / (lcm_nm/m))]):
    ans = -1
    break
else:
  ans = lcm_nm
print(ans)

Submission status: Time Limit Exceeded

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

    for i in range(lcm(n,m)):
        if i%nn == 0 and i%mm == 0 and s[i//nn] != t[i//mm]:
            print(-1)
            return
    print(nmlcm)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N,M=(int(i) for i in input().split())
S=input()
T=input()
gcd_NM=gcd(N,M)
L=(N*M//gcd_NM)
LN=[1+(L//N)*i for i in range(N)]
LM=[1+(L//M)*i for i in range(M)]
L_NM=list(set(LN)&set(LM))
A=True
for i in L_NM:
  if S[LN.index(i)]!=T[LM.index(i)]:
    A=False
    break
if A is True:
  print(L)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

p = lcm(N, M)
i = 0
z = 1
flag = 1
while flag == 1:
    if N>M:
        if N%M == 0:
            if z > 2:
                print(-1)
                exit()
    else:
        if M%N == 0:
            if z > 2:
                print(-1)
                exit()

    p *= z
    li_s = []
    li_t = []
    flag = 0
    for i in range(len(S)):
        li_s.append(int(p/N*i))

    for i in range(len(T)):
        li_t.append(int(p/M*i))
    for i in li_s:
        if i in li_t:
            if S[li_s.index(i)] != T[li_t.index(i)]:
                flag = 1
    z += 1

print(p)

Submission status: Time Limit Exceeded

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

def gcd(a, b):
    x = max(a, b)
    y = min(a, b)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z


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

p = lcm(N, M)
i = 0
z = 1
flag = 1
while flag == 1:
    if N>M:
        if N%M == 0:
            if z > 2:
                print(-1)
                exit()
    else:
        if M%N == 0:
            if z > 2:
                print(-1)
                exit()

    p *= z
    li_s = []
    li_t = []
    flag = 0
    for i in range(len(S)):
        li_s.append(int(p/N*i))

    for i in range(len(T)):
        li_t.append(int(p/M*i))
    for i in li_s:
        if i in li_t:
            if S[li_s.index(i)] != T[li_t.index(i)]:
                flag = 1
    z += 1

print(p)

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)

def atwo(n,m,s,t):
    l=lcm(n,m)
    a=l/n
    b=l/m
    for i in range(n):
        for j in range(m):
            if a*i==b*j:
                if s[i]==t[j]:
                    pass
                else:
                    l=-1

    return l

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

Submission status: Time Limit Exceeded

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(lcm):
    if i % N_gap == 0 and i % M_gap == 0:
        if S[i//N_gap] != T[i//M_gap]:
            print(-1)
            exit()
print(lcm_base(N, M))

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions

n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()
t = sys.stdin.readline()

l = n*m//fractions.gcd(n, m)
s_index = [((i*l//n) + 1) for i in range(n)]
t_index = [((i*l//m) + 1) for i in range(m)]
for e in s_index:
    if e in t_index and s[s_index.index(e)] != t[t_index.index(e)]:
        print(-1)
        sys.exit()
print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions

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


n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()
t = sys.stdin.readline()

l = lcm(n, m)
s_index = [((i*l//n) + 1) for i in range(n)]
t_index = [((i*l//m) + 1) for i in range(m)]
for e in s_index:
    if e in t_index and s[s_index.index(e)] != t[t_index.index(e)]:
        print(-1)
        sys.exit()
print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions

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


n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()
t = sys.stdin.readline()

l = lcm(n, m)
s_index = [((i*l//n) + 1) for i in range(n)]
t_index = [((i*l//m) + 1) for i in range(m)]
for e in s_index:
    if e in t_index:
        if s[s_index.index(e)] != t[t_index.index(e)]:
            print(-1)
            sys.exit()
print(l)

Submission status: Time Limit Exceeded

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, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()
t = sys.stdin.readline()

l = lcm(n, m)
s_index = [((i*l//n) + 1) for i in range(n)]
t_index = [((i*l//m) + 1) for i in range(m)]
for e in s_index:
    if e in t_index:
        if s[s_index.index(e)] != t[t_index.index(e)]:
            print(-1)
            sys.exit()
print(l)

Submission status: Time Limit Exceeded

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

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

l = lcm(n, m)
numS = [1]
numT = [1]

for i in range(1, n):
    num = i * l // n + 1
    numS.append(num)

for i in range(1, m):
    num = i * l // m + 1
    numT.append(num)
    
dictS = {}
dictT = {}

for i in range(n):
    dictS[numS[i]] = S[i]

for i in range(m):
    dictT[numT[i]] = T[i]
    
ans = l
for i in dictS:
    for j in dictT:
        if i == j:
            if dictS[i] != dictT[j]:
                ans = -1
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
S = input(); T = input()
gcd = fractions.gcd(N,M)
N_prime = N //gcd; M_prime = M // gcd
for i in range(0,N,N_prime):
    for j in range(0,M,M_prime):
        if i * M_prime - j * N_prime == 0 and S[i] != T[j]:
            print(-1)
            exit()
print(N*M // gcd)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n: d[o].add(s[i])
    if i<m: d[p].add(t[i])
    if i<n and len(d[o])==2: f=-1
    if i<m and len(d[p])==2: f=-1
print(f)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

tmp = n * m // fractions.gcd(n, m)
array = ["" for x in range(tmp)]
for i, j in zip(range(0, tmp, tmp // n), range(n)):
    array[i] = s[j]
for i, j in zip(range(0, tmp, tmp // m), range(m)):
    if array[i] != t[j] and array[i] != "":
        print(-1)
        exit()
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# https://img.atcoder.jp/agc028/editorial.pdf
N, M = map(int,input().split())
S = input()
T = input()

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

A = [None for i in range(L)]
for n in range(N):
  index =  L*n//N 
  if A[index] is None:
    A[index] = S[n]
  else:
    print(-1)
    exit()

for m in range(M):
  index =  L*m//M
  if A[index] is None or A[index] == T[m]:
    A[index] = T[m]
  else:
    print(-1)
    exit()

print(len(A))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
S=input()
T=input()
list_S=list(S)
list_T=list(T)
Number_i=[i for i in range(N)]
Number_j=[j for j in range(M)]
Kaburi_i=[]
Kaburi_j=[]
counter=0
Flag=0
for i in Number_i:
  if i*M/N in Number_j:
    Kaburi_i.append(i)
    Kaburi_j.append(int(i*M/N))
Kaburi_Size=len(Kaburi_i)
while counter<=Kaburi_Size-1:
  if list_S[Kaburi_i[counter]]==list_T[Kaburi_j[counter]]:
    pass
  else:
    Flag=1
    break
  counter+=1
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
if Flag==1:
  print(-1)
else:
  print(int(N*M/gcd(N,M)))

Submission status: Time Limit Exceeded

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

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

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

i = 1
while True:
    exist = True
    for j in range(L*i):
        if j % int(L/N) == 0 and j % int(L/M) == 0 and S[int(j*N/L)] != T[int(j*M/L)]:
            exist = False
            break
    if exist == True:
        print (L*i)
        exit()
    elif L*1 > 10 ** 5:
       print (-1)
       exit()
    else:
        i = i + 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

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

    if b == 1:
        return 1
    m = a % b
    if m == 0:
        return b
    return gcd(b, m)


def main():
    N, M = [int(a) for a in input().split()]

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(L):
        if i % cc != 0:
            continue
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

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

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


def main():
    N, M = [int(a) for a in input().split()]

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(L):
        if i % cc != 0:
            continue
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

s = list(input())
t = list(input())

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

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

l = lcm(n,m)

x = ['' for _ in range(l)]
step = l // n
for i in range(n):
    x[i * step] = s[i]

#print(x)
step = l // m
for i in range(m):
    if x[i * step] != t[i] and x[i * step] != '':
        print(-1)
        exit()

print(l)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd
 
 
N, M = list(map(int, input().split()))
S = input()
T = input()
N = len(S)
M = len(T)
s = []
t = []
L = int(N * M / gcd(N, M))
 
 
x = [0 for i in range(L)]
 
tmplen = N if N >= M else M
 
if tmplen == N:
    for i in range(tmplen):
        num = int(i * (L / N))
        x[num] = S[i]
    otherlen = M
    for j in range(otherlen):
        num = int(j * (L/M))
        if x[num] != 0 and x[num] != T[j]:
            L = -1
            break
else:
    for i in range(tmplen):
        num = int(i * (L / M))
        x[num] = T[i]
    otherlen = N
    for j in range(otherlen):
        num = int(j * (L/N))
        if x[num] != 0 and x[num] != S[j]:
            L = -1
            break
print(L)

Submission status: Time Limit Exceeded

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


def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    x = ['' for _ in range(size)]

    for i in range(n):
        x[i * size // n] = s[i]

    for j in range(m):
        if x[j * size // m] == '':
            x[j * size // m] = t[j]
        elif x[j * size // m] != t[j]:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
n, m = map(int, input().split())
listS = list(input())
listT = list(input())
listX = []


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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import copy

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 = canditates_s
canditates_t = copy.copy(canditates_s) 
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
 
n, m = (int(i) for i in input().split()) 

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

s = input()
t = input()

i = 0
while i <= len(ind_list) - 1:
    if s[int(i / (lcm / n))] != t[int(i / (lcm / m))]:
        break
    i += 1
 
if i == len(ind_list):
    print(int(lcm))
else:
    print(-1)