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: Wrong Answer

Solution code:
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+1)*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)
            exit()

    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)

Submission status: Wrong Answer

Solution code:
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+1)*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)
            exit()

    memo=[-1 for i in range(0,n)]
    def dfs(num):
        if memo[num]!=-1:
            return memo[num]

        if not bool[num]:
            memo[num]=0
            return memo[num]
        else:
            ans=1+dfs((num+m)%n)
            memo[num]=ans
            return memo[num]

    answer=0
    for i in range(0,n):
        answer=max(answer,dfs(i))
    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)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)

s=input()
t=input()
n=len(s)
m=len(t)

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

for i in range(0,n):
    if flag[i]:
        flag[i]=False
        x=(i+m)%n
        while x!=i:
            flag[x]=False
            if not bool[x]:
                break
            else:
                x=(x+m)%n
        else:
            print(-1)
            exit()


memo=[-1 for i in range(0,n)]
def dfs(num):
    if memo[num]!=-1:
        return memo[num]

    if not bool[num]:
        memo[num]=0
        return memo[num]
    else:
        ans=1+dfs((num+m)%n)
        memo[num]=ans
        return memo[num]

ans=0
for i in range(0,n):
    ans=max(ans,dfs(i))
print(ans)

Submission status: Wrong Answer

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

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 1)
else:
    ss = s

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

def contain(a, b):
    """Checks that string a contains string b"""
    B = 10 ** 9 + 7

    # Length
    al = len(a)
    bl = len(b)
    if al < bl:
        return []
    
    # Calculate B^bl
    t = B ** bl
    
    # First hash
    ah = 0
    bh = 0
    for i in range(bl):
        ah = ah * B + ord(a[i])
        bh = bh * B + ord(b[i])
    
    # Roll
    indices = []
    for i in range(al - bl + 1):
        if ah == bh:
            indices.append(i)
            
        if i < al - bl:
            ah = ah * B + ord(a[i + bl]) - ord(a[i]) * t
        
    return indices


if len(s) < len(t):
    s, t = t, s
x = contain(s * 2, t)

if len(x) == 0:
    print(0)
else:
    d = [x[i + 1] - x[i] for i in range(len(x) - 1)]
    if all(d[0] == d[i] for i in range(len(d))):
        print(-1)
    else:
        res = 0
        tmp = 0
        l = len(t)
        for i in range(len(x) - 1):
            if x[i + 1] - x[i] == l:
                tmp += 1
            else:
                res = max(res, tmp + 1)
                tmp = 0

        print(max(res, tmp + 1))

Submission status: Wrong Answer

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 main():
    S = input().strip()
    T = input().strip()
    LT = len(T)
    k = max(1, (LT - 1) // len(S) + 1)

    SS = S * k
    LS = len(SS)
    j = 0
    res = V(max)
    tmp = 0
    first = None
    while True:
        if j != 0 and j % LS == 0:
            break
               
        j %= LS

        if j + LT <= LS:
            if SS[j:j + LT] == T:
                tmp += 1
                j += LT
            else:
                if first is None:
                    first = tmp
                res.ud(tmp)
                tmp = 0
                j += 1
        else:
            if SS[j:] == T[:LS - j] and SS[:LT - LS + j] == T[LS - j:]:
                tmp += 1
                j += LT
            else:
                if first is None:
                    first = tmp
                res.ud(tmp)
                tmp = 0
                j += 1
    if first is None:
        print(-1)
    else:
        res.ud(tmp + first)
        print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    s = S()
    t = S()
    while len(s) <= len(t):
        s += s
    ns = len(s)
    nt = len(t)
    z = Z_algorithm(t+s*2)[nt:]
    z = [1 if z[i] >= len(t) else 0 for i in range(ns)]
    dp = [0]*ns
    dp[0] = z[0]
    f = [1]*ns
    for i in range(ns):
        s = set()
        x = i
        while f[x]:
            f[x] = 0
            s.add(x)
            x += nt
            if x >= ns:
                x %= ns
        if s and all([z[x] for x in s]):
            print(-1)
            return
    for i in range(ns):
        ni = i+nt
        if ni >= ns:
            ni %= ns
        if z[ni]:
            dp[ni] = dp[i]+1
    print(max(dp))
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    ns = len(s)
    nt = len(t)
    z = Z_algorithm(t+s*2)[nt:]
    z = [1 if z[i] >= len(t) else 0 for i in range(ns)]
    dp = [0]*ns
    dp[0] = z[0]
    f = [1]*ns
    for i in range(ns):
        s = set()
        x = i
        while f[x]:
            f[x] = 0
            s.add(x)
            x += nt
            if x >= ns:
                x %= ns
        if s and all([z[x] for x in s]):
            print(-1)
            return
    for i in range(ns):
        ni = i+nt
        if ni >= ns:
            ni %= ns
        if z[ni]:
            dp[ni] = dp[i]+1
    print(max(dp))
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    ns = len(s)
    nt = len(t)
    z = Z_algorithm(t+s*2)[nt:]
    z = [1 if z[i] >= len(t) else 0 for i in range(ns)]
    dp = [0]*ns
    dp[0] = z[0]
    f = [1]*ns
    for i in range(ns):
        s = set()
        x = i
        while f[x]:
            f[x] = 0
            s.add(x)
            x += nt
            if x >= ns:
                x %= ns
        if all([z[x] for x in s]):
            print(-1)
            return
    for i in range(ns):
        ni = i+nt
        if ni >= ns:
            ni %= ns
        if z[ni]:
            dp[ni] = dp[i]+1
    print(max(dp))
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    ns = len(s)
    nt = len(t)
    z = Z_algorithm(t+s*2)[nt:]
    z = [1 if z[i] >= len(t) else 0 for i in range(ns)]
    dp = [0]*ns
    dp[0] = z[0]
    for i in range(ns):
        ni = i+nt
        if ni >= ns:
            ni %= ns
        if z[ni]:
            dp[ni] = dp[i]+1
    if min(dp) > 0:
        print(-1)
    else:
        print(max(dp))
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    def dfs(i):
        res = 0
        ni = i+nt
        if ni >= ns:
            ni %= ns
        if now[ni]:
            res = float("inf")
        else:
            if z[ni]:
                now[ni] = 1
                d[ni] = 1
                dfs(ni)
                now[ni] = 0
                res = ans[ni]+1
            else:
                res = 1
        ans[i] = res

    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    ns = len(s)
    nt = len(t)
    z = Z_algorithm(t+s*2)[nt:]
    z = [1 if z[i] >= len(t) else 0 for i in range(ns)]
    ans = [0]*ns
    for i in range(ns):
        if z[i] and not ans[i]:
            ans[i] = 1
            m = 1
            x = i
            while 1:
                x += nt
                if x >= ns:
                    x %= ns
                if not z[x]:
                    break
                if m < ans[x]:
                    m = ans[x]
                else:
                    ans[x] = m = m+1
                if m > len(s)*10:
                    print(-1)
                    return
            ans[i] = m
    m = max(ans)
    print(m)
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    ns = len(s)
    nt = len(t)
    z = Z_algorithm(t+s*3)[nt:]
    n = 2*ns
    z = [1 if z[i] >= len(t) else 0 for i in range(n)]
    dp = [0]*n
    dp[0] = z[0]
    for i in range(n):
        ni = i+nt
        if ni >= n:
            continue
        if z[ni]:
            dp[ni] = dp[i]+1
    for i in range(ns,n):
        if dp[i-nt]+1 != dp[i]:
            print(max(dp))
            return
    print(-1)
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    s = S()
    t = S()
    ns = len(s)
    while len(s) < len(t):
        s += s
    nt = len(t)
    z = Z_algorithm(t+s*3)[nt:]
    n = 2*len(s)
    z = [1 if z[i] >= len(t) else 0 for i in range(n)]
    dp = [0]*n
    dp[0] = z[0]
    for i in range(n):
        ni = i+nt
        if ni >= n:
            continue
        if z[ni]:
            dp[ni] = dp[i]+1
    ans = max(dp)
    if ans >= ns:
        print(-1)
    else:
        print(ans)
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        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
        return z
    s = S()
    t = S()
    ns = len(s)
    while len(s) < len(t):
        s += s
    nt = len(t)
    z = Z_algorithm(t+s*3)[nt:]
    n = 2*len(s)
    z = [1 if z[i] >= len(t) else 0 for i in range(n)]
    dp = [0]*n
    dp[0] = z[0]
    for i in range(n):
        ni = i+nt
        if ni >= n:
            continue
        if z[ni]:
            dp[ni] = dp[i]+1
    ans = max(dp)
    if ans >= ns+1:
        print(-1)
    else:
        print(ans)
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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

def solve():
    s = S()
    t = S()
    ns = len(s)
    nt = len(t)
    f = {chr(i+ord("a")):i+1 for i in range(26)}
    for i in range(ns):
        s[i] = f[s[i]]
    for i in range(nt):
        t[i] = f[t[i]]
    b = 27
    mod1 = 1000000007
    mod2 = 1000000009
    invb1 = pow(b,mod1-2,mod1)
    invb2 = pow(b,mod2-2,mod2)
    pownt1 = pow(b,nt,mod)
    invnt1 = pow(pownt1,mod1-2,mod1)
    powns1 = pow(b,ns,mod1)
    invns1 = pow(powns1,mod1-2,mod1)
    pownt2 = pow(b,nt,mod2)
    invnt2 = pow(pownt2,mod2-2,mod2)
    powns2 = pow(b,ns,mod2)
    invns2 = pow(powns2,mod2-2,mod2)
    l = 0
    r = ns+2
    while r > l+1:
        m = (l+r) >> 1
        n = m*nt
        st = [m]*nt
        ms = n//ns
        rs = n-ms*ns
        ss = [ms+1 if i < rs else ms for i in range(ns)]
        pow1 = pow(b,n*mod1,mod1)
        pows1 = pow(pownt1,m,mod1)
        f1 = pow1*(pows1-1)*pow(pows1*(1-invnt1),mod1-2,mod1)%mod1
        pow2 = pow(b,n*mod2,mod2)
        pows2 = pow(pownt2,m,mod2)
        f2 = pow2*(pows2-1)*pow(pows2*(1-invnt2),mod2-2,mod2)%mod2
        h1 = 0
        h2 = 0
        for i in range(nt):
            ti = t[i]
            f1 *= invb1
            f1 %= mod1
            h1 += ti*f1
            h1 %= mod1
            f2 *= invb2
            f2 %= mod2
            h2 += ti*f2
            h2 %= mod2
        pows1 = pow(powns1,ms,mod1)
        f1 = pow1*(pows1-1)*pow(pows1*(1-invns1),mod1-2,mod1)%mod1
        pows2 = pow(powns2,ms,mod2)
        f2 = pow2*(pows2-1)*pow(pows2*(1-invns2),mod2-2,mod2)%mod2
        k1 = 0
        k2 = 0
        for i in range(ns):
            if not ss[i]:
                break
            si = s[i]
            f1 *= invb1
            f1 %= mod1
            k1 += si*f1
            k1 %= mod1
            f2 *= invb2
            f2 %= mod2
            k2 += si*f2
            k2 %= mod2
        k1_ = 0
        k2_ = 0
        for i in range(rs):
            si = s[i]
            k1_ *= b
            k1_ += si
            k1_ %= mod1
            k2_ *= b
            k2_ += si
            k2_ %= mod2
        k1 += k1_
        k1 %= mod
        k2 += k2_
        k2 %= mod
        p1 = pow(b,n-1,mod1)
        p2 = pow(b,n-1,mod2)
        k = 0
        for j in range(rs,ns+rs):
            if (h1,h2) == (k1,k2):
                l = m
                break
            i = j%ns
            si = s[i]
            sk = s[k]
            k1 -= sk*p1%mod1
            k1 *= b
            k1 += si
            k1 %= mod1
            k2 -= sk*p2%mod2
            k2 *= b
            k2 += si
            k2 %= mod2
            k += 1
        else:
            r = m
    if l == ns+1:
        print(-1)
    else:
        print(l)
    return

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

Submission status: Wrong Answer

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:
            idx.append(i-nt+1)
    if len(idx) == 1:
        print(0)
        exit()
    ans = 1
    ans_ = 1
    ns_ = ns // 2
    dic = {}
    for i in range(1, len(idx)):
        if idx[i] - nt in dic:
            tmp = dic[idx[i]-nt] + 1
            dic[idx[i]] = tmp
            if idx[i] <= ns_-nt:
                ans = max(ans, tmp)
                ans_ = max(ans_, tmp)
            else:
                ans_ = max(ans_, tmp)
        else:
            dic[idx[i]] = 1
    if ans_ == ans:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()