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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10*6)
INF = float("inf")


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


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


class Graph(object):
    # 無向グラフを仮定する。
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。

        self.E[始点]は、[終点, 重み]を要素としたリスト
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def tree_diameter(g):
    """木gの直径を求める
    """
    def visit(prev, v):
        """
        prev: 一つ手前の頂点
        v: 今の頂点
        """
        most_t, most_w = 0, 0   # 最も遠い頂点を控える
        for dst, weight in g.E[v]:  # 頂点vから伸びる枝の中で
            if dst == prev:        # 一つ手前のprevに伸びる枝を覗いて
                continue
            t, w = visit(v, dst)  # 再帰的に求める。返り値は最も遠い頂点とそこまでの距離
            w += weight           # 今の枝の距離を加えて
            if most_w < w:        # 遠さが更新されれば
                most_t, most_w = t, w  # 更新
        return most_t, most_w

    far_v, dist = visit(-1, 0)
    far_v, dist = visit(-1, far_v)
    return dist


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    LCM = S*T//GCD(S, T)
    if s*(LCM//S) == t*(LCM//T):
        print(-1)
        return

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    g = Graph(S)
    for m in match:
        g.add_edge([m % S, (m+T) % S])

    d = tree_diameter(g)
    print(d+1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
INF = float("inf")


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


class Graph(object):
    # 無向グラフを仮定する。
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。

        self.E[始点]は、[終点, 重み]を要素としたリスト
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def tree_diameter(g):
    """木gの直径を求める
    """
    def visit(prev, v):
        """
        prev: 一つ手前の頂点
        v: 今の頂点
        """
        most_t, most_w = 0, 0   # 最も遠い頂点を控える
        for dst, weight in g.E[v]:  # 頂点vから伸びる枝の中で
            if dst == prev:        # 一つ手前のprevに伸びる枝を覗いて
                continue
            t, w = visit(v, dst)  # 再帰的に求める。返り値は最も遠い頂点とそこまでの距離
            w += weight           # 今の枝の距離を加えて
            if most_w < w:        # 遠さが更新されれば
                most_t, most_w = t, w  # 更新
        return most_t, most_w

    far_v, dist = visit(-1, 0)
    far_v, dist = visit(-1, far_v)
    return dist


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    LCM = S*T//GCD(S, T)
    if s*(LCM//S) == t*(LCM//T):
        print(-1)
        return

    # Zアルゴリズムなどを陽に使わなくとも、findでいけるか？
    s2 = s+s
    match = []
    pos = s2.find(t, 0)
    while 0 <= pos < S:
        match.append(pos)
        pos = s2.find(t, pos+1)

    if len(match) == 0:
        # とも限らないけどなー。
        # s = "ABC"
        # t = "ABCABCABC"
        # でもこれなら無限か
        print(0)
        return

    g = Graph(S)
    for m in match:
        g.add_edge([m, (m+T) % S])

    d = tree_diameter(g)
    print(d+1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd

def main():
  s = input()
  t = input()
  sl = len(s)
  tl = len(t)


  def min_circ(a):
      for i in range(1, len(a)+1):
          if len(a) % i == 0:
              if a[:i] * (len(a)//i) == a:
                  return i


  tc = min_circ(t)
  if len(s) % tc == 0:
      if t[:tc]*(len(s)//min_circ(t)) == s:
          print(-1)
          sys.exit()


  s *= tl//sl + 5
  s *= 3

  sl = len(s)
  count = 0
  ans = 0

  r = 0
  while r + tl <= sl-1:
      if s[r:r+tl] == t:
          count += 1
          ans = max(ans, count)
          r += tl
      else:
          count = 0
          r += 1

  print(ans)

if __name__ == "__main__"
  main()

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd

def main():
  s = input()
  t = input()
  sl = len(s)
  tl = len(t)


  def min_circ(a):
      for i in range(1, len(a)+1):
          if len(a) % i == 0:
              if a[:i] * (len(a)//i) == a:
                  return i


  tc = min_circ(t)
  if len(s) % tc == 0:
      if t[:tc]*(len(s)//min_circ(t)) == s:
          print(-1)
          sys.exit()


  s *= tl//sl + 5
  s *= 3

  sl = len(s)
  count = 0
  ans = 0

  r = 0
  while r + tl <= sl-1:
      if s[r:r+tl] == t:
          count += 1
          ans = max(ans, count)
          r += tl
      else:
          count = 0
          r += 1

  print(ans)

if __name__ == "__main__"

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
 
import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase
 
import __pypy__

def partial(S):
    P = [0] * len(S)
    g = 0
    for i in range(1, len(S)):
        while g and (S[g] != S[i]):
            g = P[g - 1]
        P[i] = g = g + (S[g] == S[i])

    return p

def match(S, pattern):
    if not pattern: return list(range(len(S)))
    P = partial(pattern)
    g = 0
    ret = []
    
    for i in range(len(S)):
        while g and pattern[g] != S[i]:
            g = P[g - 1]
        g += pattern[g] == S[i]
        if g == len(P): 
            ret.append(i + 1 - g)
            g = P[g - 1]
    
    return ret

 
def main():
    s = input()
    t = input()
 
    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3
 
    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if not match(s, u):
            hi = mi
        else:
            lo = mi + 1
 
    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return
 
    print(lo - 1)
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()
 
 
class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)
 
    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()
 
 
def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()
 
 
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
S = input()
W = input()
S *= 6


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
p = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        p = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    # print("i =", i)
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3 > len(S) * 2:
    print(-1)
else:
    print(cmax//0)

Submission status: Runtime Error

Solution code:
S = input()
W = input()
S *= 6


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
k = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        k = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3> len(S) * 2:
    print(-1)
else:
    print(cmax//k)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
 
import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase
 
import __pypy__
 
def pi(s):
    p = [0] * len(s)
    g = 0
    for i in range(1, len(s)):
        while g and (s[i] != s[g]):
            g = p[g - 1]
        g += s[i] == s[g]
        p[i] = g

    return p

def match(s, pat):
    ret = []
    p = pi(pat)
    g = 0
    for i in range(len(s)):
        while g and s[i] != pat[g]:
            g = p[g - 1]
        g += s[i] == pat[g]
        if g == len(pat): 
            ret.append(i + 1 - g)
            g = p[g - 1]
    return ret
 
def main():
    s = input()
    t = input()
 
    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3
 
    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if not match(s, u):
            hi = mi
        else:
            lo = mi + 1
 
    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return
 
    print(lo - 1)
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()
 
 
class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)
 
    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()
 
 
def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()
 
 
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
S = input()
W = input()
S *= 3

T = [-1] * len(W)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 2 > len(S) * 3:
    print(-1)
else:
    print(cmax)

Submission status: Runtime Error

Solution code:
S = input()
W = input()
S *= 2

T = [-1] * len(W)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 2 > len(S):
    print(-1)
else:
    print(cmax)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    s_ = [s[i] for i in range(len(s))]
    while len(s) < len(t):
        s += s_
    mod1 = 1000000007
    mod2 = 1000000009
    pm1 = [1]
    pm2 = [1]
    for i in range(1000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    m_ = len(s)
    l = 0
    max_m = 2*len(s)
    r = math.ceil(max_m/n_)+1
    mod_n = [i%n_ for i in range(1000001)]
    mod_m = [i%m_ for i in range(1000001)]
    while r-l > 1:
        if l*n_ >= max_m:
            print(-1)
            return
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[mod_n[i]]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[mod_n[i]]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[mod_m[i]]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[mod_m[i]]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,max_m+1):
                hash1 = (hash1*pm1[1]-d[s[mod_m[i-n]]]*pm1[n]+d[s[mod_m[i]]])%mod1
                hash2 = (hash2*pm2[1]-d[s[mod_m[i-n]]]*pm2[n]+d[s[mod_m[i]]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    if l*n_ >= max_m:
        print(-1)
        return
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
 
import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase
 
import __pypy__
 
 
def main():
    s = input()
    t = input()
 
    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3
 
    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if u not in s:
            hi = mi
        else:
            lo = mi + 1
 
    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return
 
    print(lo - 1)
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()
 
 
class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)
 
    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()
 
 
def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()
 
 
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
s = input()
t = input()

s = s*ceil(len(t)/len(s))
s = s.count(t)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    s += s
    s += s
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(3000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,len(s)):
                hash1 = (hash1*pm1[1]-d[s[i-n]]*pm1[n]+d[s[i]])%mod1
                hash2 = (hash2*pm2[1]-d[s[i-n]]*pm2[n]+d[s[i]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    if l == len(s)//n_:
        print(-1)
    else:
        print(l)
    return

#Solve
if __name__ == "__main__":
    F()