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

Solution code:
S = input()
W = input()
M = len(S)
S *= 3 * (len(W)//len(S)+1)


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) + 1:
    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
m = 0
def KMP(i0):
    global m, i
    ret = -1

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

i = 0
j = -10**9
c = 0
cmax = 0
f = 0
while m < len(S)-N:
    k = KMP(0)
    if k == len(S):
        break
    elif k == N + j:
        c += 1
    else:
        c = 1
        f += 1
    cmax = max(cmax, c)
    j = k
if f == 1:
    print(-1)
else:
    print(cmax//p)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

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

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def rolling_hash(s, w, MOD):
    ret = []
    tmp = 0
    p = pow(26, w, MOD)
    ords = [ord(c) - 97 for c in s]
    for i, o in enumerate(ords):
        tmp = tmp * 26 + o
        if i >= w:
            tmp = (tmp - ords[i - w] * p)
        tmp %= MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    k = (lt - 1) // ls + 1
    s *= k * 2
    ls *= k
    rs, rt = rolling_hash(s, lt, MOD), rolling_hash(t, lt, MOD)
    rs = rs[ls:]
    ht = rt[-1]

    checked = [-1] * ls

    def series(i, st):
        if st <= i < st + lt:
            return float('-inf')
        if checked[i] == -1:
            checked[i] = series((i + lt) % ls, st) + 1 if rs[i] == ht else 0
        return checked[i]

    for i, hs in enumerate(rs):
        if hs != ht:
            continue
        ret = series((i + lt) % ls, i)
        if ret == float('-inf'):
            return -1
        checked[i] = ret + 1

    return max(0, max(checked))


s = input()
t = input()
print(solve(s, t))

Submission status: Accepted

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]
        p[i] = g = g + (s[i] == s[g])

    return p


def match(s, pat, uniq='\0'):
    return [i + 1 - c for i, c in enumerate(pi(pat + uniq + s)[len(pat) + 1:]) if c == len(pat)]
 
 
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: Accepted

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

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):
    if not pat: return list(range(len(s)))
    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: Accepted

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

u = s * (len(t) // len(s) + 2)

t_add = t + "."


def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = word[i] == word[j]

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table


table_tx = partial_match_table(t_add)

match = [0] * len(s)

i = j = 0
while i < len(u) and j < len(t_add):
    if u[i] == t_add[j]:
        i += 1
        j += 1
    elif j == 0:
        i += 1
    else:
        j = table_tx[j]
    if j == len(t_add) - 1:
        match[(i - j) % len(s)] = 1


# search
searched = [0] * len(s)
longest = 0
infinity = False
for i in range(len(s)):
    if searched[i]:
        continue
    searched[i] = 1
    p = i
    right = 0
    while match[p]:
        right += 1
        p = (p + len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    left = 0
    p = i
    while match[(p - len(t)) % len(s)]:
        left += 1
        p = (p - len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    if left + right > longest:
        longest = left + right

if infinity:
    print(-1)
else:
    print(longest)

Submission status: Accepted

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)
    for i in range(1, len(s)):
        g = p[i - 1]
        while g and (s[i] != s[g]):
            g = p[g - 1]
        p[i] = g + int(s[i] == s[g])

    return p


def match(s, pat):
    res = []
    p = pi(pat + '\0' + s)
    for i in range(len(p) - len(s), len(p)):
        if p[i] == len(pat):
            res.append(i - 2 * len(pat))

    return res


def main():
    s = input()
    t = input()

    n = len(s)
    s *= (len(t) + 3 * len(s) - 1) // len(s)

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

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)
    for i in range(1, len(s)):
        g = p[i - 1]
        while g and (s[i] != s[g]):
            g = p[g - 1]
        p[i] = g + int(s[i] == s[g])

    return p


def match(s, pat):
    res = []
    p = pi(pat + '\0' + s)
    for i in range(len(p) - len(s), len(p)):
        if p[i] == len(pat):
            res.append(i - 2 * len(pat))

    return res


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

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def z(q):
    n = len(q)
    z = [0] * n
    if n == 0:
        return z
    z[0] = n
    ii = 1
    l = 0
    r = 0
    while ii < n:
        if r >= ii and z[ii-l] < r-ii+1:
            z[ii] = z[ii-1]
        else:
            l = ii
            if r < ii: r = ii
            while r < n and q[r-l] == q[r]:
                r += 1
            z[ii] = r-l
            r -= 1
        ii += 1
    return z

s = ns()
t = ns()
while len(s) <= len(t):
    s = s + s

zs = z(s)
zt = z(t)
zst = z(t+s+s)

pes = len(s)
for i in range(1, len(s)):
    if len(s) % i == 0 and zs[i] >= len(s)-i:
        pes = i
        break

pet = len(t)
for i in range(1, len(t)):
    if len(t) % i == 0 and zt[i] >= len(t)-i:
        pet = i
        break

# print(pes, pet)
if pes % pet == 0:
    for i in range(pet):
        if zst[len(t)+i] >= pes:
            print(-1)
            sys.exit(0)

lt = len(t)
m = s + s
while len(m) <= 4*len(t):
    m = m + m
while len(t) < len(m):
    t = t + t
# print(t, m, s)
zx = z(t+"$"+m)
# print(zx)
ans = max(zx[len(t)+1:])
print(ans//lt)

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(10**6)


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


S = input()
T = input()
REP_S = ''
target_len = len(S) + len(T) - 1
while len(REP_S) < target_len:
    REP_S += S

# Z-algorithmでREP_S中に含まれるTの場所を調べる
T_REP_S = T + REP_S
z = z_alg(T_REP_S)
location_list = list()
for i in range(len(S)):
    if z[i + len(T)] >= len(T):
        location_list.append(i)

# Tがなければ0を出力して終了
if len(location_list) == 0:
    print(0)
    exit(0)

# グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
node_flag_list = [0] * len(S)
for n in location_list:
    node_flag_list[n] = 1
node_num_list = [-1] * len(S)

def dfs(node, depth=0):
    # return (has_loop, node_num)
    if depth > len(location_list):
        return True, -1
    if node_num_list[node] >= 0:
        return False, node_num_list[node]
    next_node = (node + len(T)) % len(S)
    if node_flag_list[next_node] == 0:
        node_num_list[node] = 0
        return False, 0
    has_loop, node_num = dfs(next_node, depth + 1)
    if has_loop:
        return True, -1
    node_num_list[node] = 1 + node_num
    return False, 1 + node_num

for n in location_list:
    has_loop, _ = dfs(n)
    if has_loop:
        print(-1)
        exit(0)

print(max(node_num_list) + 1)

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(10**7)


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


def main():
    S = input()
    T = input()
    REP_S = ''
    target_len = len(S) + len(T) - 1
    while len(REP_S) < target_len:
        REP_S += S

    # Z-algorithmでREP_S中に含まれるTの場所を調べる
    T_REP_S = T + REP_S
    z = z_alg(T_REP_S)
    location_list = list()
    for i in range(len(S)):
        if z[i + len(T)] >= len(T):
            location_list.append(i)

    # Tがなければ0を出力して終了
    if len(location_list) == 0:
        print(0)
        return

    # グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
    node_flag_list = [0] * len(S)
    for node in location_list:
        node_flag_list[node] = 1
    node_num_list = [-1] * len(S)

    def dfs(node, depth=0):
        # return (has_loop, node_num)
        if depth > len(location_list):
            return True, -1
        if node_num_list[node] >= 0:
            return False, node_num_list[node]
        next_node = (node + len(T)) % len(S)
        if node_flag_list[next_node] == 0:
            node_num_list[node] = 0
            return False, 0
        has_loop, node_num = dfs(next_node, depth + 1)
        if has_loop:
            return True, -1
        n = 1 + node_num
        node_num_list[node] = n
        return False, n

    for node in location_list:
        has_loop, _ = dfs(node)
        if has_loop:
            print(-1)
            return

    print(max(node_num_list) + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(10**6)


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


def main():
    S = input()
    T = input()
    REP_S = ''
    target_len = len(S) + len(T) - 1
    while len(REP_S) < target_len:
        REP_S += S

    # Z-algorithmでREP_S中に含まれるTの場所を調べる
    T_REP_S = T + REP_S
    z = z_alg(T_REP_S)
    location_list = list()
    for i in range(len(S)):
        if z[i + len(T)] >= len(T):
            location_list.append(i)

    # Tがなければ0を出力して終了
    if len(location_list) == 0:
        print(0)
        return

    # グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
    node_flag_list = [0] * len(S)
    for node in location_list:
        node_flag_list[node] = 1
    node_num_list = [-1] * len(S)

    def dfs(node, depth=0):
        # return (has_loop, node_num)
        if depth > len(location_list):
            return True, -1
        if node_num_list[node] >= 0:
            return False, node_num_list[node]
        next_node = (node + len(T)) % len(S)
        if node_flag_list[next_node] == 0:
            node_num_list[node] = 0
            return False, 0
        has_loop, node_num = dfs(next_node, depth + 1)
        if has_loop:
            return True, -1
        n = 1 + node_num
        node_num_list[node] = n
        return False, n

    for node in location_list:
        has_loop, _ = dfs(node)
        if has_loop:
            print(-1)
            return

    print(max(node_num_list) + 1)


if __name__ == '__main__':
    main()