Problem:


Score : 600 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.

There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s.

Notes

A string a is a substring of another string b if and only if there exists an integer x (0 \leq x \leq |b| - |a|) such that, for any y (1 \leq y \leq |a|), a_y = b_{x+y} holds.

We assume that the concatenation of zero copies of any string is the empty string. From the definition above, the empty string is a substring of any string. Thus, for any two strings s and t, i = 0 satisfies the condition in the problem statement.

Constraints

1 \leq |s| \leq 5 \times 10^5

1 \leq |t| \leq 5 \times 10^5

s and t consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i; if the number is infinite, print -1.

Sample Input 1

abcabab
ab

Sample Output 1

3

The concatenation of three copies of t, ababab, is a substring of the concatenation of two copies of s, abcabababcabab, so i = 3 satisfies the condition.

On the other hand, the concatenation of four copies of t, abababab, is not a substring of the concatenation of any number of copies of s, so i = 4 does not satisfy the condition.

Similarly, any integer greater than 4 does not satisfy the condition, either. Thus, the number of non-negative integers i satisfying the condition is finite, and the maximum value of such i is 3.

Sample Input 2

aa
aaaaaaa

Sample Output 2

-1

For any non-negative integer i, the concatenation of i copies of t is a substring of the concatenation of 4i copies of s. Thus, there are infinitely many non-negative integers i that satisfy the condition.

Sample Input 3

aba
baaab

Sample Output 3

0

As stated in Notes, i = 0 always satisfies the condition.



Sample input:
abcabab
ab


Sample output:
3

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
import random

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列


    class rh:#base,max_n,convertを指定すること
        def __init__(self,base=26,max_n=2*10**5):#baseとmaxnを指定すること。baseは偶数(modが奇数)
            self.mod=random.randrange(1<<54-1,1<<55-1,2)#奇数、衝突させられないよう乱数で生成
            self.base=int(base*0.5+0.5)*2#偶数,英小文字なら26とか
            self.max_n=max_n
            self.pows1=[1]*(max_n+1)
            cur1=1
            for i in range(1,max_n+1):
                cur1=cur1*base%self.mod
                self.pows1[i]=cur1
    
        def convert(self,c): return alp2num(c,False)#大文字の場合Trueにする
        
        def get(self, s):#特定の文字のhash. O(|s|)
            n=len(s)
            mod=self.mod
            si=[self.convert(ss) for ss in s]
            h1=0
            for i in range(n):h1=(h1+si[i]*self.pows1[n-1-i])%mod
            return h1
        
        def get_roll(self, s, k):#ローリングハッシュ,特定の文字の中から長さkのhashをすべて得る,O(|s|)
            n=len(s)
            si=[self.convert(ss) for ss in s]
            mod=self.mod
            h1=0
            for i in range(k):h1=(h1+si[i%n]*self.pows1[k-1-i])%mod
            hs=[0]*n
            hs[0]=h1
            mbase1=self.pows1[k]
            base=self.base
            for i in range(1,n): 
                front=si[i-1];back=si[(i+k-1)%n]
                h1=(h1*base-front*mbase1+back)%mod
                hs[i]=h1
            return hs
    
    s=input()
    t=input()
    n=len(s)
    nt=len(t)
    rhs=rh()
    has=rhs.get(t)
    hass=rhs.get_roll(s,len(t))
    l=[hass[i]==has for i in range(len(s))]
    ds=[0]*n
    for i in range(len(s)):
        ci=i
        q=deque()
        while l[ci] and ds[ci]==0:
            q.append(ci)
            ci=(ci+nt)%n
            if ci==i:
                print(-1)
                return
        tot=ds[ci]
        while q:
            tot+=1
            ci=q.pop()
            ds[ci]=tot
    print(max(ds))
        




if __name__ == "__main__":
    
    main()

Submission status: Runtime Error

Solution code:
S = input()
T = input()
ls,lt = len(S),len(T)
ns = 0--(lt+ls)//ls

def z_algorithm(s):
    N = len(s)
    ret = [0]*N
    ret[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + ret[k]<j:
            ret[i+k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret

za = z_algorithm(T + '#' + S*ns)

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(ls)
for i in range(ls):
    if za[lt+1+i] == lt:
        j = (i+lt) % ls
        if uf.is_same(i,j): continue
        uf.unite(i,j)

from math import gcd
g = gcd(ls,lt)
ans = 0
for i in range(ls):
    sz = uf.size(i)
    if sz == ls//g:
        print(-1)
        exit()
    ans = max(ans, sz-1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
s=list(input())
t=list(input())

tsr=list(t)+list(s)
while len(tsr)<2*len(t)+len(s):
  tsr+=s
#print(tsr)

#Z[i]: 文字列Sと各S[i:]の最長共通接頭辞の長さ
def z_alg(S):
  NN=len(S)
  Z=[NN]+[0]*(NN-1)
  i,j=1,0
  while i<NN:
    while i+j<NN and S[j]==S[i+j]:
      j+=1
    if not j:
      i+=1
      continue
    Z[i]=j
    k=1
    while NN-i>k and k<j-Z[k]:
      Z[i+k]=Z[k]
      k+=1
    i+=k
    j-=k
  return Z

zlist=z_alg(tsr)
#print(zlist)

match_list=[]
for i in range(len(s)):
  match_list.append(zlist[i+len(t)]>=len(t))
#print(match_list)

graph=[[] for _ in range(len(s))]
for i in range(len(s)):
  if match_list[i]:
    graph[i].append((i+len(t))%len(s))
#print(graph)

def dfs(u,i):
  if dist[u]!=-1:
    return dist[u]
  elif not graph[u]:
    dist[u]=0
    return 0
  else:
    if i>len(s):
      print(-1)
      sys.exit(0)
    v=graph[u][0]
    res=dfs(v,i+1)
    dist[u]=1+res
    return 1+res

dist=[-1]*len(s)
for i in range(len(s)):
  if dist[i]==-1:
    dfs(i,0)
    
#print(dist)
print(max(dist))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60


def gen(a, b, num):
    import random
    result = set()
    while 1:
        while 1:
            v = random.randint(a, b)//2*2+1
            if v not in result:
                break
        for x in range(3, int(math.sqrt(v))+1, 2):
            if v % x == 0:
                break
        else:
            result.add(v)
            if len(result) == num:
                break
    return result


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            num = ord(s[i])
            tmp = (tmp*base + num) % mod
            h[i+1] = tmp

        self.pw = pw = [1]*(len(s)+1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


class RRH():
    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = gen(2, 10**3, num)
        else:
            bases = {293, 389, 167, 397, 953}

        MOD = 10**9+7
        self.rhs = [RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return [rh.calc(l, r) for rh in self.rhs]


def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (lt // ls * 2 + 1)
    srh = RRH(SS)
    th = RRH(T).calc(0, len(T))

    ok = set()
    for i in range(ls):
        if srh.calc(i, i+lt) == th:
            ok.add(i)

    ans = 0
    for s in ok:
        done = set()
        t = 1
        while True:
            if s in done:
                return -1
            elif (s + lt) % ls in ok:
                done.add(s)
                s = (s + lt) % ls
                t += 1
            else:
                break
        ans = max(ans, t)
    return ans


def main():
    S = input()
    T = input()
    print(slv(S, T))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1000000//tl + 2s
r2 = r
s *= 999999//sl + 1
n = len(s)
base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if r == r2:
    print(-1)
else:
    print(l)

Submission status: Runtime Error

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

if s*tl == t*sl:
    print(-1)
    sys.exit()
    
l = 0
r = 1000000//tl + 1
s *= 999999//sl + 1
n = len(s)
base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m


print(l)

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def f(I, s0, v, N, M, A):
    if I[v]:
        s = (v + M) % N
        if s == s0:
            return -1
        
        t = f(I, s0, s, N, M, A)
        if t == -1:
            return -1
        else:
            A[v] = True
            return t + 1
    else:
        A[v] = True
        return 0



def main():
    S = input().strip()
    T = input().strip()
    N = len(S)
    M = len(T)

    B = [0] * M
    B[0] = -1
    j = 0
    for i in range(2, M):
        if T[i - 1] == T[i]:
            B[i] = j + 1
            j += 1
            continue

        if j > 0:
            j = B[j]
        else:
            B[i] = 0

    I = [False] * N
    m = 0
    i = 0
    while m < N:
        if T[i] == S[(m + i) % N]:
            i += 1
            if i == M:
                I[m] = True
                m += 1
                i = 0
        else:
            m = m + i - B[i]
            if i > 0:
                i = B[i]

    s = 0
    A = [False] * N
    res = V(max)
    for s in range(N):
        if A[s]:
            continue
        
        t = f(I, s, s, N, M, A)
        if t == -1:
            print(-1)
            return
        res.ud(t)

    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    S = input().rstrip('\n')
    T = input().rstrip('\n')

    ns = len(S)
    nt = len(T)
    S = ''.join([S] * ((nt-1)//ns+1))
    S = ''.join([S, S, S, S])
    ns = len(S)

    mod1 = 1000000007
    mod2 = 1000000009
    mod3 = 998244353
    b1 = 1007
    b2 = 2009
    b3 = 2999
    H1 = 0
    H2 = 0
    H3 = 0
    for i, t in enumerate(T):
        t = ord(t)
        H1 = ((H1 * b1)%mod1 + t)%mod1
        H2 = ((H2 * b2)%mod2 + t)%mod2
        H3 = ((H3 * b3)%mod3 + t)%mod3
    h1 = 0
    h2 = 0
    h3 = 0
    for i in range(nt):
        s = ord(S[i])
        h1 = ((h1 * b1) % mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 + s) % mod3

    idx = [-10**10]
    if h1 == H1 and h2 == H2 and h3 == H3:
        idx.append(0)
    b1_nt = pow(b1, nt, mod1)
    b2_nt = pow(b2, nt, mod2)
    b3_nt = pow(b3, nt, mod3)
    for i in range(nt, ns):
        s = ord(S[i])
        s_prev = ord(S[i-nt])
        h1 = ((h1 * b1) % mod1 - (b1_nt * s_prev)%mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 - (b2_nt * s_prev)%mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 - (b3_nt * s_prev) % mod3 + s) % mod3
        if h1 == H1 and h2 == H2 and h3 == H3:
            if i-nt+1 - idx[-1] >= nt:
                idx.append(i-nt+1)
    if len(idx) == 1:
        print(0)
        exit()
    tmp = 1
    ans = 1
    ans_ = 1
    ns_ = ns // 2
    for i in range(1, len(idx)):
        if idx[i] - idx[i-1] == nt:
            tmp += 1
            if idx[i] < ns_:
                ans = max(ans, tmp)
                ans_ = max(ans_, tmp)
            else:
                ans_ = max(ans_, tmp)
        else:
            tmp = 1
    if ans_ == ans:
        print(ans)
    else:
        print(-1)
        assert 0


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
"""
Returns the index of the given character in the English alphabet, counting from 0.
"""
def alphabet_index(c):
    return ord(c.lower()) - 97 # 'a' is ASCII character 97

"""
Returns the length of the match of the substrings of S beginning at idx1 and idx2.
"""
def match_length(S, idx1, idx2):
    if idx1 == idx2:
        return len(S) - idx1
    match_count = 0
    while idx1 < len(S) and idx2 < len(S) and S[idx1] == S[idx2]:
        match_count += 1
        idx1 += 1
        idx2 += 1
    return match_count

"""
Returns Z, the Fundamental Preprocessing of S. Z[i] is the length of the substring 
beginning at i which is also a prefix of S. This pre-processing is done in O(n) time,
where n is the length of S.
"""
def fundamental_preprocess(S):
    if len(S) == 0: # Handles case of empty string
        return []
    if len(S) == 1: # Handles case of single-character string
        return [1]
    z = [0 for x in S]
    z[0] = len(S)
    z[1] = match_length(S, 0, 1)
    for i in range(2, 1+z[1]): # Optimization from exercise 1-5
        z[i] = z[1]-i+1
    # Defines lower and upper limits of z-box
    l = 0
    r = 0
    for i in range(2+z[1], len(S)):
        if i <= r: # i falls within existing z-box
            k = i-l
            b = z[k]
            a = r-i+1
            if b < a: # b ends within existing z-box
                z[i] = b
            elif b > a: # Optimization from exercise 1-6
                z[i] = min(b, len(S)-i)
                l = i
                r = i+z[i]-1
            else: # b ends exactly at end of existing z-box
                z[i] = b+match_length(S, a, r+1)
                l = i
                r = i+z[i]-1
        else: # i does not reside within existing z-box
            z[i] = match_length(S, 0, i)
            if z[i] > 0:
                l = i
                r = i+z[i]-1
    return z

"""
Generates R for S, which is an array indexed by the position of some character c in the 
English alphabet. At that index in R is an array of length |S|+1, specifying for each
index i in S (plus the index after S) the next location of character c encountered when
traversing S from right to left starting at i. This is used for a constant-time lookup
for the bad character rule in the Boyer-Moore string search algorithm, although it has
a much larger size than non-constant-time solutions.
"""
def bad_character_table(S):
    if len(S) == 0:
        return [[] for a in range(26)]
    R = [[-1] for a in range(26)]
    alpha = [-1 for a in range(26)]
    for i, c in enumerate(S):
        alpha[alphabet_index(c)] = i
        for j, a in enumerate(alpha):
            R[j].append(a)
    return R

"""
Generates L for S, an array used in the implementation of the strong good suffix rule.
L[i] = k, the largest position in S such that S[i:] (the suffix of S starting at i) matches
a suffix of S[:k] (a substring in S ending at k). Used in Boyer-Moore, L gives an amount to
shift P relative to T such that no instances of P in T are skipped and a suffix of P<nowiki>[:L[i]]</nowiki>
matches the substring of T matched by a suffix of P in the previous match attempt.
Specifically, if the mismatch took place at position i-1 in P, the shift magnitude is given
by the equation len(P) - L[i]. In the case that L[i] = -1, the full shift table is used.
Since only proper suffixes matter, L[0] = -1.
"""
def good_suffix_table(S):
    L = [-1 for c in S]
    N = fundamental_preprocess(S[::-1]) # S[::-1] reverses S
    N.reverse()
    for j in range(0, len(S)-1):
        i = len(S) - N[j]
        if i != len(S):
            L[i] = j
    return L

"""
Generates F for S, an array used in a special case of the good suffix rule in the Boyer-Moore
string search algorithm. F[i] is the length of the longest suffix of S[i:] that is also a
prefix of S. In the cases it is used, the shift magnitude of the pattern P relative to the
text T is len(P) - F[i] for a mismatch occurring at i-1.
"""
def full_shift_table(S):
    F = [0 for c in S]
    Z = fundamental_preprocess(S)
    longest = 0
    for i, zv in enumerate(reversed(Z)):
        longest = max(zv, longest) if zv == i+1 else longest
        F[-i-1] = longest
    return F

"""
Implementation of the Boyer-Moore string search algorithm. This finds all occurrences of P
in T, and incorporates numerous ways of pre-processing the pattern to determine the optimal 
amount to shift the string and skip comparisons. In practice it runs in O(m) (and even 
sublinear) time, where m is the length of T. This implementation performs a case-insensitive
search on ASCII alphabetic characters, spaces not included.
"""
def string_search(P, T):
    if len(P) == 0 or len(T) == 0 or len(T) < len(P):
        return []

    matches = []

    # Preprocessing
    R = bad_character_table(P)
    L = good_suffix_table(P)
    F = full_shift_table(P)

    k = len(P) - 1      # Represents alignment of end of P relative to T
    previous_k = -1     # Represents alignment in previous phase (Galil's rule)
    while k < len(T):
        i = len(P) - 1  # Character to compare in P
        h = k           # Character to compare in T
        while i >= 0 and h > previous_k and P[i] == T[h]:   # Matches starting from end of P
            i -= 1
            h -= 1
        if i == -1 or h == previous_k:  # Match has been found (Galil's rule)
            matches.append(k - len(P) + 1)
            return matches
            k += len(P)-F[1] if len(P) > 1 else 1
        else:   # No match, shift by max of bad character and good suffix rules
            char_shift = i - R[alphabet_index(T[h])][i]
            if i+1 == len(P):   # Mismatch happened on first attempt
                suffix_shift = 1
            elif L[i+1] == -1:   # Matched suffix does not appear anywhere in P
                suffix_shift = len(P) - F[i+1]
            else:               # Matched suffix appears in P
                suffix_shift = len(P) - L[i+1]
            shift = max(char_shift, suffix_shift)
            previous_k = k if shift >= i+1 else previous_k  # Galil's rule
            k += shift
    return matches


# https://snuke.hatenablog.com/entry/2014/12/03/214243
def z_algorithm(s):
    a = [0] * len(s)
    a[0] = len(s)
    i = 1
    j = 0
    while i < len(s):
        while i+j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a


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

import sys

if __name__ == "__main__":
    s = input()
    t = input()
    n = max(2, (len(t)*2 + len(s) - 1) // len(s))
    s2 = s * n
    a = z_algorithm(s2)
    m = string_search(t, s2)
    min_cyle = len(s)
    for i, a_v in enumerate(a[1:len(s)]):
        if a_v >= len(s):
            min_cycle = i+1
            break
    print("min_cycle={}".format(min_cycle), file=sys.stderr)

    if len(m) == 0:
        print(0)
    elif len(t) % min_cycle == 0:
        print(-1)
    else:
        print(len(s) // gcd(len(s), len(t)))