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.

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def z_algo(S):  
    
    
    
    
    i, j, n = 1, 0, len(S)
    Z = np.zeros(S.shape, dtype=np.int64)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(s, t):
    ns = len(s)
    nt = len(t)
    n = max(ns, nt) * 2
    ts = np.empty(n*4, dtype=np.int64)
    ts[:n*2] = t[np.arange(2*n, dtype=np.int64) % nt]
    ts[n*2:] = s[np.arange(2*n, dtype=np.int64) % ns]
    Z = z_algo(ts)
    ma = Z[n*2:].max()
    if ma > n:
        return -1
    else:
        return ma // nt

numba_compile([
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8(i1[:],i1[:])"],
])

def main():
    s = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    t = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    ans = solve(s, t)
    print(ans)

main()

Solution (Python):
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

    
    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)

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

    
    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)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
import random

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

def main():
    mod = 1000000007
    

    
    
    
    
    


    class rh:
        def __init__(self,base=26,max_n=5*10**5):
            self.mod=random.randrange(1<<54-1,1<<55-1,2)
            self.base=int(base*0.5+0.5)*2
            self.max_n=max_n
            self.pows1=[1]*(max_n+1)
            cur1=1
            for i in range(1,max_n+1):
                cur1=cur1*base%self.mod
                self.pows1[i]=cur1
    
        def convert(self,c): return alp2num(c,False)
        
        def get(self, s):
            n=len(s)
            mod=self.mod
            si=[self.convert(ss) for ss in s]
            h1=0
            for i in range(n):h1=(h1+si[i]*self.pows1[n-1-i])%mod
            return h1
        
        def get_roll(self, s, k):
            n=len(s)
            si=[self.convert(ss) for ss in s]
            mod=self.mod
            h1=0
            for i in range(k):h1=(h1+si[i%n]*self.pows1[k-1-i])%mod
            hs=[0]*n
            hs[0]=h1
            mbase1=self.pows1[k]
            base=self.base
            for i in range(1,n): 
                front=si[i-1];back=si[(i+k-1)%n]
                h1=(h1*base-front*mbase1+back)%mod
                hs[i]=h1
            return hs
    
    s=input()
    t=input()
    n=len(s)
    nt=len(t)
    rhs=rh()
    has=rhs.get(t)
    hass=rhs.get_roll(s,nt)
    l=[hass[i]==has for i in range(n)]
    ds=[0]*n
    for i in range(n):
        ci=i
        q=deque()
        while l[ci] and ds[ci]==0:
            q.append(ci)
            ci=(ci+nt)%n
            if ci==i:
                print(-1)
                return
        tot=ds[ci]
        while q:
            tot+=1
            ci=q.pop()
            ds[ci]=tot
    print(max(ds))
        




if __name__ == "__main__":
    
    main()

Solution (Python):



def RollingHash(S, T, ls):
    if len(S) < len(T):
        return []
    
    h = 10**11+7
    b = 10**7+7
    L = len(T)

    bL = 1
    for i in range(L):
        bL = bL * b % h

    hashS = 0
    for i in range(L):
        hashS = (hashS * b + S[i]) % h

    hashT = 0
    for i in range(L):
        hashT = (hashT * b + T[i]) % h
    
    correctIndexes = [0]*len(S)
    ret = 0
    if hashS == hashT:
        correctIndexes[0] = 1
    for j in range(len(S)-L):
        hashS = (hashS * b - S[j]*bL + S[L+j]) % h
        if hashS == hashT:
            tmp = correctIndexes[j+1-L] + 1
            correctIndexes[j+1] = tmp
            if tmp > ret: ret = tmp
    if ret*L > 2*ls:
        return -1
    return ret


import sys
input = sys.stdin.buffer.readline

S = input().rstrip()
T = input().rstrip()

ls = len(S)
lt = len(T)
S = S*((2*lt+3*ls-1)//ls)
ans = RollingHash(S, T, ls)
print(ans)

Solution (Python):
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    def KMP(S, word):
        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 = partial_match_table(word)
        
        i, p = 0, 0
        match = []
        while (i < len(S) and p < len(word)):
            
            if S[i] == word[p]:
                i += 1;
                p += 1
                if p == len(word):
                    match.append(i - p)
                    p = table[p]
            else:
                if p == 0:
                    i += 1
                else:
                    p = table[p]

        return match

    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            

        def reset(self):
            self.parent = [-1] * len(self.parent)

        def find(self, x):
            
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            
            return self.find(x) == self.find(y)

        def size(self, x):
            
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            
            return self.parent[x] < 0

        def roots(self):
            
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            
            return len(self.roots())

        def all_group_members(self):
            
            return {r: self.members(r) for r in self.roots()}

    S = SI()
    T = SI()
    if len(S)<len(T):
        S *= (len(T)//len(S))+1
    
    N = len(S)
    n = len(T)
    V = [[]for _ in range(N)]
    S *= 2
    kmp = KMP(S,T)
    

    for i in kmp:
        if i>=N:
            continue
        V[i%N].append((i+n)%N)
    uf = UnionFind(N)
    

    def dfs(s):
        cnt = 0
        for v in V[s]:
            
            if uf.same(s,v):
                return -1
            
            if uf.size(v)>1:
                
                cnt = uf.size(v)
                uf.unite(s, v)
                return cnt
            else:
                uf.unite(s, v)
                child = dfs(v)
            if child==-1:
                return -1
            cnt = child+1
        return cnt

    ans = 0
    for i in range(N):
        if uf.size(i)!=1:
            continue
        cur = dfs(i)
        
        if cur==-1:
            print(-1)
            return
        if ans<cur:
            ans = cur
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examF()

"""
abababababc
babababa
"""

Solution (Python):
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  
    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[top] = right
        left = 1
        
        if right == 0:
            top += 1
            continue
        
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        
        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)
        exit()
print(max(dp))

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens + lent) * 2
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent * 2 - 1:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens+lent) * 2 + 1
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent * 2:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
S = input().rstrip()
T = input().rstrip()

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

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

def solve():
    ls,lt = len(S),len(T)
    ns = 0--(lt+ls)//ls

    za = z_algorithm(T + '

    from fractions import gcd
    g = gcd(ls,lt)
    uf = UnionFind(ls)
    match = False
    for i in range(ls):
        if za[lt+1+i] == lt:
            match = True
            j = (i+lt) % ls
            if uf.is_same(i,j):
                if uf.size(i) == ls//g:
                    print(-1)
                    exit()
                continue
            uf.unite(i,j)
    if not match:
        print(0)
        exit()

    ans = 0
    for i in range(ls):
        ans = max(ans, uf.size(i)-1)
    print(ans)

solve()

Solution (Python):
def construct_table(n, s):
    table = [-1] * (n + 1)
    j = -1
    for i in range(n):
        while j >= 0 and s[i] != s[j]:
            j = table[j]
        j += 1
        table[i + 1] = j
    return table


s = input()
t = input()
n = len(s)
m = len(t)
s2 = s * ((max(m, n) + m) // n + 1)
tb = construct_table(m, t)
l = [False] * n
i = 0
j = 0
while i < n:
    if t[j] != s2[i + j]:
        i += j - tb[j]
        if j > 0:
            j = tb[j]
    else:
        j += 1
        if j == m:
            l[i] = True
            i += j - tb[j]
            j = tb[j]
inv = [0] * n
for i in range(n):
    if l[i]:
        t = (i + m) % n
        i = t
        inv[t] += 1
ans = 0
v = [0] * n
for i in range(n):
    if inv[i] == 0:
        v[i] = 1
        r = 0
        while l[i]:
            r += 1
            t = (i + m) % n
            v[t] = 1
            i = t
        ans = max(ans, r)
if 0 in v:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import defaultdict

mod1 = 10 ** 9 + 7
base1 = 1007

def getlist():
	return list(map(int, input().split()))

class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)
		self.judge = "No"

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x); y = self.find(y)
		if self.rank[x] < self.rank[y]:
			if self.same_check(x, y) != True:
				self.size[y] += self.size[x]
				self.size[x] = 0
			else:
				self.judge = "Yes"
			self.par[x] = y
		else:
			if self.same_check(x, y) != True:
				self.size[x] += self.size[y]
				self.size[y] = 0
			else:
				self.judge = "Yes"
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def siz(self, x):
		x = self.find(x)
		return self.size[x]


def rollingHash(N, M, A):
	mul1 = 1
	for i in range(M):
		mul1 = (mul1 * base1) % mod1

	val1 = 0
	for i in range(M):
		val1 = val1 * base1 + A[i]
		val1 %= mod1

	hashList1 = [None] * (N - M + 1)
	hashList1[0] = val1

	for i in range(N - M):
		val1 = (val1 * base1 - A[i] * mul1 + A[i + M]) % mod1
		hashList1[i + 1] = val1

	return hashList1


def main():
	s = list(input())
	t = list(input())
	N = len(s)
	M = len(t)
	
	if N < M:
		var = int(M // N) + 1
		s = s * var
		N = N * var
	
	s = s + s
	for i in range(2 * N):
		s[i] = ord(s[i]) - 97
	for i in range(M):
		t[i] = ord(t[i]) - 97

	sHash1 = rollingHash(2 * N, M, s)
	tHash1 = rollingHash(M, M, t)
	tHash1 = tHash1[0]


	value = "No"
	UF = UnionFind(N)
	for i in range(N):
		j = (i + M) % N
		if sHash1[i] == tHash1:
			value = "Yes"
			if sHash1[j] == tHash1:
				UF.union(i, j)

	if value == "No":
		print(0)
		return

	if UF.judge == "Yes":
		print(-1)
		return

	for i in range(N):
		UF.par[i] = UF.find(i)
	ans = 0
	for i in range(N):
		ans = max(ans, UF.size[i])

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
s=list(input())
t=list(input())

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



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

zlist=z_alg(tsr)


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


path=[-1]*len(s)
for i in range(len(s)):
  if match_list[i]:
    path[i]=(i+len(t))%len(s)


dist=[-1]*len(s)
for i in range(len(s)):
  if dist[i]!=-1:
    continue
    
  d=0
  offset=0
  stack=[i]
  ii=i
  while path[ii]!=-1:
    if d>len(s):
      print(-1)
      sys.exit(0)
    elif dist[ii]!=-1:
      offset=dist[ii]
      break    
    ii=path[ii]
    stack.append(ii)
    d+=1
  
  cnt=0
  while stack:
    p=stack.pop()
    dist[p]=offset+cnt
    cnt+=1
    

print(max(dist))

Solution (Python):

import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60

class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

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

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

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

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

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

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

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



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



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

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



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



if __name__ == '__main__':
    main()

Solution (Python):

import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60

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

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

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

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

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

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RRH.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

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

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



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



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

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



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



if __name__ == '__main__':
    main()