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-----
abcabab
ab

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

# 適当な素数と原始根でrolling hash
MOD = 10 ** 9 + 993
base = 123450

S = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)
T = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)

# Sの方が長くする
LS = len(S)
LT = len(T)
n = (LT + (-LT) % LS) // LS
S = np.concatenate([S]*(n+1))
S = S[:LS+LT]

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2); arr = arr.reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

base_inv = pow(base,MOD-2,MOD)
x = np.full(LS+LT,base,dtype=np.int64)
x[0] = 1
power = cumprod(x)
x = np.full(LS+LT,base_inv,dtype=np.int64)
x[0] = 1
power_inv = cumprod(x)

def to_rolling_hash(S):
    return (S * power[:len(S)] % MOD).cumsum() % MOD

S_hash = to_rolling_hash(S)
T_hash = to_rolling_hash(T)[-1] # 文字列全体

S_hash_LT = S_hash[LT-1:]
S_hash_LT[1:] -= S_hash.copy()[:LS]
S_hash_LT %= MOD
S_hash_LT *= power_inv[:LS+1]
S_hash_LT %= MOD

INF = 10 ** 18
visited = [False] * LS
dist = [INF] * LS # 操作終了位置からの距離

q = np.where(S_hash_LT[:LS] != T_hash)[0].tolist()

d = 0
while q:
    qq = []
    for x in q:
        if dist[x] == INF:
            dist[x] = d
            qq.append((x-LT)%LS)
    d += 1
    q = qq

answer = max(dist)
if answer >= INF:
    answer = -1

print(answer)

s = input()
t = input()

base = 3
MOD = 1004535809

def rolling_hash(s, base, MOD):
    l = len(s)
    h = [0]*(l + 1)
    for i in range(l):
        h[i+1] = (h[i] * base + ord(s[i])) % MOD
    return h

s = s * ((len(t) + len(s) - 1)//len(s) * 2)
rh0 = rolling_hash(s, base, MOD)
B = 0
for c in t:
    B = (B * base + ord(c)) % MOD
N = len(s)//2
M = len(t)
R = [0]*N
L = pow(base, M, MOD)
r = 0
for i in range(N):
    if (rh0[i+M] - rh0[i]*L) % MOD == B:
        R[i] = 1
if not any(R):
    print(0)
    return

S = []
for i in range(N):
    if R[i-M] and R[i] == 0:
        S.append((i - M) % N)
if not S:
    print(-1)
    return

ans = 0
for v in S:
    d = 1
    while R[v-M]:
        d += 1
        v = (v - M) % N
    ans = max(ans, d)
print(ans)

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

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0
    results = []
    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
            if p == len(word):
                p = table[p]
                results.append((i-len(word), i))
        elif p == 0:
            i += 1
        else:
            p = table[p]
    return results

inf = 10**18
s = input().strip()
t = input().strip()
m=(len(t)+len(s)-1+len(s)-1)//len(s)
d = set()
for a, b in kmp_search(m*s, t):
    d.add(a%len(s))

d2 = set()
for i in range(len(s)):
    if i not in d:
        d2.add(i)
q = d2

LT, LS = len(t), len(s)
dist = [inf] * LS
d = 0
while q:
    qq = []
    for x in q:
        if dist[x] == inf:
            dist[x] = d
            qq.append((x-LT)%LS)
    d += 1
    q = qq

answer = max(dist)
if answer >= inf:
    answer = -1

print(answer)


class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        l = len(s)
        self.pw = pw = [1]*(l+1)
        self.h = h = [0]*(l+1)
        for i in range(l):
            h[i+1] = (h[i] * base + ord(s[i])) % mod
            pw[i+1] = pw[i] * base % mod

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

def main():
  s = input()
  t = input()
  ls,lt = len(s), len(t)
  m = (ls+lt-1)//ls + 1
  s *= m
  s1 = RollingHash(s, 1007, 10**9+7)
  t1 = RollingHash(t, 1007, 10**9+7)
  w = t1.get(0,lt)
  g = [None]*ls
  for i in range(ls):
    if s1.get(i, i+lt) == w:
      g[i] = (i+lt)%ls
  
  f = [None]*ls
  for i in range(ls):
    if f[i] is None:
      f[i] = ls
      q = [i]
      while q:
        if g[q[-1]] is None:
          f[q[-1]] = 0
          q.pop()
        elif f[g[q[-1]]] is None:
          q.append(g[q[-1]])
        else:
          f[q[-1]] = f[g[q[-1]]] + 1
          q.pop()
  print(max(f) if max(f) < ls else -1)
  return
  
main()

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

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0
    results = []
    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
            if p == len(word):
                p = table[p]
                results.append((i-len(word), i))
        elif p == 0:
            i += 1
        else:
            p = table[p]
    return results

inf = 10**18
s = input().strip()
t = input().strip()
m=(len(t)+len(s)-1+len(s)-1)//len(s)
d = [-1] * (len(s)+1) 
for a, b in kmp_search(m*s, t):
    a, b = a%len(s)+1, b%len(s)+1
    d[a] = b


ls = [-1]*(len(s)+1)
vs = set()
for i in range(1, len(s)+1):
    if i in vs:
        continue
    c = 0
    j = i
    while True:
        vs.add(i)
        i = d[i]
        if i == -1:
            break
        c += 1
        if i == j:
            c = inf
            break
        if ls[i] != -1:
            c += ls[i]
            break
    if c == inf:
        break
    ls[j] = c
print((max(ls) if c != inf else -1))


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


def getTableMP(Ss):
    lenS = len(Ss)
    table = [-1] * (lenS+1)
    j = -1
    for i in range(lenS):
        while j >= 0 and Ss[i] != Ss[j]:
            j = table[j]
        j += 1
        table[i+1] = j
    return table


Ss = input()
Ts = input()

lenS, lenT = len(Ss), len(Ts)
num = (lenT+lenS-1+lenS-1)//lenS
S2s = Ss * num

tableMP = getTableMP(Ts + '$' + S2s)

isFounds = [False] * lenS
for i in range(2*lenT+1, 2*lenT+lenS+1):
    if tableMP[i] >= lenT:
        isFounds[i-2*lenT-1] = True

ans = 0
numDone = 0
for i in range(lenS):
    if not isFounds[i]:
        i = (i+lenT)%lenS
        for num in range(lenS+1):
            if not isFounds[i]:
                ans = max(ans, num)
                numDone += num+1
                break
            i = (i+lenT)%lenS
        else:
            ans = -1
            break

if numDone < lenS:
    ans = -1
print(ans)


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 n in location_list:
        node_flag_list[n] = 1
    depth_list = [-1] * len(S)
    for n in location_list:
        if depth_list[n] >= 0:
            continue
        cur_node = n
        d, has_loop = 0, False
        while node_flag_list[cur_node] == 1:
            depth_list[cur_node] = d
            d += 1
            cur_node = (cur_node + len(T)) % len(S)
            if cur_node == n:
                has_loop = True
                break
        if has_loop:
            print(-1)
            return

    print(max(depth_list) + 1)


def __starting_point():
    main()
__starting_point()

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    left = 0  # 左の箱の左端(本当はここでので宣言は不要だけど理解の為)
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 箱の幅が0だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
        left = 0  # これも本当は不要
    return lcp

def dfs(i,si):
    dp[i]=0
    ni=(i+tn)%sn
    if lcp[tn+1+ni]!=tn:return False
    if ni==si:return True
    if dp[ni]==-1 and dfs(ni,si):return True
    dp[i]=dp[ni]+1

s=SI()
t=SI()
ss = s
while len(ss) < len(s) + len(t): ss += s
lcp = LcpByZ(t + "@" + ss)
sn = len(s)
tn = len(t)
dp=[-1]*sn
for i in range(sn):
    if dp[i]!=-1:continue
    if dfs(i,i):
        print(-1)
        return
print(max(dp))


def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

import sys
from fractions import gcd

sys.setrecursionlimit(1500000)

s=input()
t=input()
n=len(s)
m=len(t)
if n!=m:
    s=(m//n+2)*s
    data=Z_algorithm(t+'?'+s)
    bool=[False for i in range(0,n)]
    for i in range(m+1,m+1+n):
        if data[i]==m:
            bool[i-m-1]=True

    g=gcd(n,m)
    for i in range(0,g):
        for j in range(0,n//g):
            if not bool[i+j*g]:
                break
        else:
            print((-1))
            return

    ans=[[] for i in range(0,g)]
    for i in range(0,g):
        ans[i].append(bool[i])
        x=(i+m)%n
        while x!=i:
            ans[i].append(bool[x])
            x=(x+m)%n

    from itertools import groupby
    answer=0
    for i in range(0,g):
        a=groupby(ans[i])
        d=[]
        for key,group in a:
            g=len(list(group))
            d.append([key,g])
        if d:
            if d[0][0] and d[-1][0]:
                d[-1][1]+=d[0][1]
        for j in range(len(d)):
            if d[j][0]:
                answer=max(answer,d[j][1])
    print(answer)


else:
    s=2*s
    data=Z_algorithm(t+'?'+s)
    for i in range(m+1,n+m+1):
        if data[i]==m:
            print((-1))
            break
    else:
        print((0))


def getTableKMP(Ss):
    Ss += '$'
    lenS = len(Ss)
    table = [-1] * lenS
    j = -1
    for i in range(lenS-1):
        while j >= 0 and Ss[i] != Ss[j]:
            j = table[j]
        j += 1
        if Ss[i+1] == Ss[j]:
            table[i+1] = table[j]
        else:
            table[i+1] = j
    return table

def getPosPtnsKMP(Ss, ptn, table):
    anss = []
    lenS, lenP = len(Ss), len(ptn)
    iS, iP = 0, 0
    while iS < lenS:
        if Ss[iS] == ptn[iP]:
            iS += 1
            iP += 1
            if iP == lenP:
                anss.append(iS-lenP)
                iP = table[iP]
        else:
            iP = table[iP]
            if iP == -1:
                iS += 1
                iP = 0
    return anss


Ss = input()
Ts = input()

lenS, lenT = len(Ss), len(Ts)
num = (lenT+lenS-1+lenS-1) // lenS
S2s = Ss * num

tableKMP = getTableKMP(Ts)
posPtns = getPosPtnsKMP(S2s, Ts, tableKMP)

isFounds = [False] * lenS
for pos in posPtns:
    if pos >= lenS:
        break
    isFounds[pos] = True

ans = 0
numDone = 0
for i in range(lenS):
    if not isFounds[i]:
        i = (i+lenT) % lenS
        for num in range(lenS+1):
            if not isFounds[i]:
                ans = max(ans, num)
                numDone += num+1
                break
            i = (i+lenT) % lenS
        else:
            ans = -1
            break

if numDone < lenS:
    ans = -1
print(ans)