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: Time Limit Exceeded

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

#Nの文字からなる文字列AのM文字のハッシュ値を計算
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)
	#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 = 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()

Submission status: Time Limit Exceeded

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)
for i in range(len(s)):
  if match_list[i]:
    path[i]=(i+len(t))%len(s)
#print(path)

dist=[-1]*len(s)
for i in range(len(s)):
  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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
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)

graph=[[] for _ in range(len(s))]
for i in range(len(s)):
  if match_list[i]:
    graph[i].append((i+len(t))%len(s))
#print(graph)

def dfs(u,i):
  if dist[u]!=-1:
    return dist[u]
  elif not graph[u]:
    dist[u]=0
    return 0
  else:
    if i>len(s):
      print(-1)
      sys.exit(0)
    v=graph[u][0]
    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:
    dfs(i,0)
    
#print(dist)
print(max(dist))

Submission status: Time Limit Exceeded

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 = {}
    for s in sorted(ok):
        ss = s
        t = 1
        way = [ss]
        while True:
            if s in done:
                t += done[s] - 1
                break
            elif (s + lt) % ls in ok:
                s = (s + lt) % ls
                if s == ss:
                    return -1
                way.append(s)
                t += 1
            else:
                for i, w in enumerate(way):
                    done[w] = t - i
                break
        ans = max(ans, t)
    return ans

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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
    for s in ok:
        done = set()
        t = 1
        while True:
            if s in done:
                return -1
            elif (s + lt) % ls in ok:
                done.add(s)
                s = (s + lt) % ls
                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: Time Limit Exceeded

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 [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
    for s in ok:
        done = set()
        t = 1
        while True:
            if s in done:
                return -1
            elif (s + lt) % ls in ok:
                done.add(s)
                s = (s + lt) % ls
                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: Time Limit Exceeded

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, 397, 953}

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

    def calc(self, l, r):
        return [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
    for s in ok:
        done = set()
        t = 1
        while True:
            if s in done:
                return -1
            elif (s + lt) % ls in ok:
                done.add(s)
                s = (s + lt) % ls
                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: Time Limit Exceeded

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+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)
            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: Time Limit Exceeded

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)
if n!=m:
    s=(m//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
            if bool[i]:
                x=(i+m)%n
                while x!=i:
                    if not flag[x]:
                        break
                    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)
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: Time Limit Exceeded

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//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
        if bool[i]:
            x=(i+m)%n
            while x!=i:
                if not flag[x]:
                    break
                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: Time Limit Exceeded

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//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
        if bool[i]:
            x=(i+m)%n
            while x!=i:
                if not bool[x] or not flag[x]:
                    break
                else:
                    x=(x+m)%n
                flag[x]=False
            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: Time Limit Exceeded

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)
ss = s
while len(ss) < n:
    ss += s
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: Time Limit Exceeded

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()
    ns = len(s)
    nt = len(t)
    ss = s*((nt//ns)+1)
    ns = len(ss)
    z = Z_algorithm(t+ss*2)[nt:]
    z = [1 if z[i] >= len(t) else 0 for i in range(ns)]
    ans = [0]*ns
    d = [0]*ns
    now = [0]*ns
    for i in range(ns):
        if z[i] and not d[i]:
            d[i] = 1
            now[i] = 1
            dfs(i)
            now[i] = 0
    m = max(ans)
    if m == float("inf"):
        print(-1)
    else:
        print(m)
    return

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

Submission status: Time Limit Exceeded

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
    d = [0]*ns
    now = [0]*ns
    for i in range(ns):
        if z[i] and not d[i]:
            d[i] = 1
            now[i] = 1
            dfs(i)
            now[i] = 0
    m = max(ans)
    if m == float("inf"):
        print(-1)
    else:
        print(m)
    return

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

Submission status: Time Limit Exceeded

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,k):
        if k > len(s)+10:
            ans[i] = float("inf")
            return
        ni = i+nt
        ni %= ns
        if z[ni]:
            dfs(ni,k+1)
        ans[i] = max(ans[i],k)
        return

    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]:
            dfs(i,1)
    m = max(ans)
    if m == float("inf"):
        print(-1)
    else:
        print(m)
    return

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

Submission status: Time Limit Exceeded

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,k):
        if k > len(s)+10:
            ans[i] = float("inf")
            return
        ni = i+nt
        ni %= ns
        if z[ni]:
            dfs(ni,k+1)
        ans[i] = max(ans[i],k)
        return

    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]:
            dfs(i,1)
    m = max(ans)
    if m == float("inf"):
        print(-1)
    else:
        print(m)
    return

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