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:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

    u = SI()
    t = SI()
    s = u * 2
    if len(s) < len(t):
        s = s + u * ((len(s)-len(t))//len(u) + 1)
    lens = len(s)
    lent = len(t)

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

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

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and i >= lent:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

    u = SI()
    t = SI()
    s = u * 2
    if len(s) > len(t):
        s = s + u * ((len(s)-len(t))//len(u) + 1)
    lens = len(s)
    lent = len(t)

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

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

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and i >= lent:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

    u = SI()
    t = SI()
    s = u * 2
    while len(s) < len(t):
        s = s + u
    lens = len(s)
    lent = len(t)

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

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

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and i >= lent:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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()
    s = s * 2
    lens = len(s)
    lent = len(t)

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

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

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and i < lent:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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()
    s = s * 2
    lens = len(s)
    lent = len(t)

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

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

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and last_i > 0:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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()
    s = s * 3
    lens = len(s)
    lent = len(t)

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

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

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and last_i > 0:
                cnt = 0
                f = True
    if f:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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()
    s = s * 2
    lens = len(s)
    lent = len(t)

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

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

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent:
                cnt = 0
                f = True
    if f:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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 + '#' + S*ns)

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

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

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 + '#' + S*ns)

    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): continue
            uf.unite(i,j)
    if not match:
        print(0)
        exit()

    from fractions import gcd
    g = gcd(ls,lt)
    ans = 0
    for i in range(ls):
        sz = uf.size(i)
        if sz == ls//g:
            print(-1)
            exit()
        ans = max(ans, sz-1)
    print(ans)

solve()

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
ls,lt = len(S),len(T)
ns = 0--(lt+ls)//ls

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

za = z_algorithm(T + '#' + S*ns)

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

uf = UnionFind(ls)
for i in range(ls):
    if za[lt+1+i] == lt:
        j = (i+lt) % ls
        if uf.is_same(i,j): continue
        uf.unite(i,j)

from fractions import gcd
g = gcd(ls,lt)
ans = 0
for i in range(ls):
    sz = uf.size(i)
    if sz == ls//g:
        print(-1)
        exit()
    ans = max(ans, sz-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")
#法と基数設定
mod1 = 10 ** 9 + 7; mod2 = 10 ** 9 + 9
base1 = 1007; base2 = 2009

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]

#Nの文字からなる文字列AのM文字のハッシュ値を計算
def rollingHash(N, M, A):
	mul1 = 1; mul2 = 1
	for i in range(M):
		mul1 = (mul1 * base1) % mod1
		mul2 = (mul2 * base2) % mod2

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

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

	for i in range(N - M):
		val1 = (val1 * base1 - A[i] * mul1 + A[i + M]) % mod1
		val2 = (val2 * base2 - A[i] * mul2 + A[i + M]) % mod2
		hashList1[i + 1] = val1
		hashList2[i + 1] = val2
		
	return hashList1, hashList2


#処理内容
def main():
	s = list(input())
	t = list(input())
	N = len(s)
	M = len(t)
	#sのほうを長く調整
	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, sHash2 = rollingHash(2 * N, M, s)
	tHash1, tHash2 = rollingHash(M, M, t)
	tHash1 = tHash1[0]
	tHash2 = tHash2[0]

	# print(sHash1)
	# print(sHash2)
	# print(tHash1)
	# print(tHash2)

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

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

Submission status: Wrong Answer

Solution code:
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
#print(tsr)

#Z[i]: 文字列Sと各S[i:]の最長共通接頭辞の長さ
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)
#print(zlist)

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

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

dist=[-1]*len(s)
for i in range(len(s)):
  if path_rev[i]!=-1:
    continue
  
  d=0
  ii=i
  while path[ii]!=-1:
    if d>len(s):
      print(-1)
      sys.exit(0)
    elif dist[ii]!=-1:
      d+=dist[ii]
      break
    ii=path[ii]
    d+=1
  dist[i]=d
    
#print(dist)
print(max(dist))

Submission status: Wrong Answer

Solution code:
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
#print(tsr)

#Z[i]: 文字列Sと各S[i:]の最長共通接頭辞の長さ
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)
#print(zlist)

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

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

max_dist=-1
for i in range(len(s)):
  if path_rev[i]==-1:
    dist=0
    ii=i
    while path[ii]!=-1:
      ii=path[ii]
      dist+=1
    max_dist=max(dist,max_dist)
    
#print(dist)
print(max_dist)

Submission status: Wrong Answer

Solution code:
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
#print(tsr)

#Z[i]: 文字列Sと各S[i:]の最長共通接頭辞の長さ
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)
#print(zlist)

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

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

def dfs(u,i):
  if dist[u]!=-1:
    return dist[u]
  elif path[u]==-1:
    dist[u]=0
    return 0
  else:
    if i>len(s):
      print(-1)
      sys.exit(0)
    v=path[u]
    res=dfs(v,i+1)
    dist[u]=1+res
    return 1+res

dist=[-1]*len(s)
for i in range(len(s)):
  if dist[i]==-1 and path_rev[i]==-1:
    dfs(i,0)
    
#print(dist)
print(max(dist))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60


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


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


class RRH():
    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = gen(2, 10**3, num)
        else:
            bases = {293, 389, 167}

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

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


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

    ok = set()
    for i in range(ls):
        if srh.calc(i, i+lt) == th:
            ok.add(i)

    ans = 0
    done = set()
    for s in sorted(ok):
        ss = s
        t = 1
        while True:
            if s in done:
                break
            elif (s + lt) % ls in ok:
                done.add(s)
                s = (s + lt) % ls
                if s == ss:
                    return -1
                t += 1
            else:
                break
        ans = max(ans, t)
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1000000//tl + 1
r2 = r
s *= 999999//sl + 2
n = len(s)

base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if r == r2:
    print(-1)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1000000//tl + 2
r2 = r
s *= 999999//sl + 2
n = len(s)

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

tc = min_circ(t)

base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if r == r2:
    print(-1)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1000000//tl + 1
r2 = r
s *= 999999//sl + 1
n = len(s)

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

tc = min_circ(t)

if t[:tc]*(1000001//tc) in s*3:
    print(-1)
    sys.exit()


base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m


print(l)

Submission status: Wrong Answer

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1000000//tl + 1
r2 = r
s *= 999999//sl + 1
n = len(s)

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

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


base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m


print(l)

Submission status: Wrong Answer

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1000000//tl + 2
r2 = r
s *= 999999//sl + 1
n = len(s)
base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if r == r2:
    print(-1)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1000000//tl + 1
r2 = r
s *= 999999//sl + 1
n = len(s)
base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if r == r2:
    print(-1)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)


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


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


l = 0
r = 1000000//tl + 1
s *= 999999//sl + 1
n = len(s)
base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m


print(l)