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:
#!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
    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)]
        p1 = pow(b,n,mod1)
        #p2 = pow(b,n,mod2)
        h1 = 0
        #h2 = 0
        for i in range(nt):
            ti = t[i]
            pow1 = pow(b,(n-i)*mod1,mod1)
            pows1 = pow(pownt1,st[i],mod1)
            h1 += ti*pow1*(pows1-1)*pow(pows1*(1-invnt1),mod1-2,mod1)%mod1
            h1 %= mod1
            """
            pow2 = pow(b,(n-i)*mod2,mod2)
            pows2 = pow(pownt2,st[i],mod2)
            h2 += ti*pow2*(pows2-1)*pow(pows2*(1-invnt2),mod2-2,mod2)%mod2
            h2 %= mod2
            """
        k1 = 0
        #k2 = 0
        for i in range(ns):
            if not ss[i]:
                break
            si = s[i]
            pow1 = pow(b,(n-i)*mod1,mod1)
            pows1 = pow(powns1,ss[i],mod1)
            k1 += si*pow1*(pows1-1)*pow(pows1*(1-invns1),mod1-2,mod1)%mod1
            k1 %= mod1
            """
            pow2 = pow(b,(n-i)*mod2,mod2)
            pows2 = pow(powns2,ss[i],mod2)
            k2 += si*pow2*(pows2-1)*pow(pows2*(1-invns2),mod2-2,mod2)%mod2
            k2 %= mod2
            """
        k = 0
        for j in range(rs,ns+rs):
            #if (h1,h2) == (k1,k2):
            if h1 == k1:
                l = m
                break
            i = j%ns
            si = s[i]
            sk = s[k]
            k1 -= sk*p1%mod1
            k1 += si
            k1 *= b
            k1 %= mod1
            """
            k2 -= sk*p2%mod2
            k2 += si
            k2 *= b
            k2 %= mod2
            """
            k += 1
        else:
            r = m
    if l == ns+1:
        print(-1)
    else:
        print(l)
    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():
    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 = 10
    mod1 = 1000000007
    mod2 = 1000000009
    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)]
        p1 = pow(b,n,mod1)
        p2 = pow(b,n,mod2)
        h1 = 0
        h2 = 0
        for i in range(nt):
            ti = t[i]
            pow1 = pow(b,(n-i)*mod1,mod1)
            pows1 = pow(pownt1,st[i],mod1)
            h1 += ti*pow1*(pows1-1)*pow(pows1*(1-invnt1),mod1-2,mod1)%mod1
            h1 %= mod1
            pow2 = pow(b,(n-i)*mod2,mod2)
            pows2 = pow(pownt2,st[i],mod2)
            h2 += ti*pow2*(pows2-1)*pow(pows2*(1-invnt2),mod2-2,mod2)%mod2
            h2 %= mod2
        k1 = 0
        k2 = 0
        for i in range(ns):
            if not ss[i]:
                break
            si = s[i]
            pow1 = pow(b,(n-i)*mod1,mod1)
            pows1 = pow(powns1,ss[i],mod1)
            k1 += si*pow1*(pows1-1)*pow(pows1*(1-invns1),mod1-2,mod1)%mod1
            k1 %= mod1
            pow2 = pow(b,(n-i)*mod2,mod2)
            pows2 = pow(powns2,ss[i],mod2)
            k2 += si*pow2*(pows2-1)*pow(pows2*(1-invns2),mod2-2,mod2)%mod2
            k2 %= 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 += si
            k1 *= b
            k1 %= mod1
            k2 -= sk*p2%mod2
            k2 += si
            k2 *= b
            k2 %= mod2
            k += 1
        else:
            r = m
    if l == ns+1:
        print(-1)
    else:
        print(l)
    return

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

Submission status: Time Limit Exceeded

Solution code:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

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

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [-1 for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i] = (i+nt)%ns

path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if path_len[i] == 0:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
from math import ceil
import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

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

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [[] for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i].append((i+nt)%ns)

path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur]:
		if adj[cur][0] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur][0]] > 0:
			path_len[x] = path_len[adj[cur][0]] + res
			return path_len[adj[cur][0]] + res
		cur = adj[cur][0]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if path_len[i] == 0:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
from math import ceil
import sys
def input():
	return sys.stdin.readline()[:-1]

sys.setrecursionlimit(10**7)

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

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

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
#print(s_concat)
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [[] for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i].append((i+nt)%ns)
		#adj[(i+nt)%ns].append(i)

#print(adj)
#visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x, root):
	if not adj[x]:
		return 0
	v = adj[x][0]
	if v == root:
		print(-1)
		sys.exit()
	else:
		path_len[x] = dfs(v, root) + 1
		return path_len[x]

ans = 0
for i in range(ns):
	if path_len[i] == 0:
		d = dfs(i, i)
		#print(d)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
from math import ceil
import sys
sys.setrecursionlimit(10**7)

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

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

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [[] for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i].append((i+nt)%ns)

path_len = [0 for _ in range(ns)]

def dfs(x, root):
	if not adj[x]:
		return 0
	v = adj[x][0]
	if v == root:
		print(-1)
		sys.exit()
	else:
		path_len[x] = dfs(v, root) + 1
		return path_len[x]

ans = 0
for i in range(ns):
	if path_len[i] == 0:
		d = dfs(i, i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1
    while j < len(word):
        matched = word[i] == word[j]
        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i
    return table

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

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


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

Submission status: Time Limit Exceeded

Solution code:
def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1
    while j < len(word):
        matched = word[i] == word[j]
        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i
    return table

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0

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

inf = 10**18
s = input().strip()
t = input().strip()
m=(len(t)+len(s)-1+len(s)-1)//len(s)
es = set()
d = [set() for _ in range(len(s)+1)]
d2 = [set() for _ in range(len(s)+1)]
#print(t, m*s)
#print(kmp_search(m*s, t))
for a, b in kmp_search(m*s, t):
    a, b = a%len(s)+1, b%len(s)+1
    es.add((a, b))
    d[a].add(b)
    d2[b].add(a)

#print(es)
fs = set()
r = 0
for x in range(len(s)+1):
    if x in fs:
        continue
    vs = set()
    vs.add(x)
    fs.add(x)
    depths = [inf]*(len(s)+1)
    depths[x] = 0
    stack = [x]
    mt = x
    while stack:
        v = stack.pop()
        if v > 0:
            for u in d[v]:
                if u in vs:
                    r = inf
                    break
                stack.append(-v)
                stack.append(u)
                depths[u] = depths[v] + 1
                if depths[u] > depths[mt]:
                    mt = u
                vs.add(u)
                fs.add(u)
        else:
            pass
    vs = set()
    vs.add(mt)
    depths = [inf]*(len(s)+1)
    depths[mt] = 0
    stack = [mt]
    mt2 = mt
    while stack:
        v = stack.pop()
        if v > 0:
            for u in d2[v]:
                if u in vs:
                    r = inf
                    break
                stack.append(-v)
                stack.append(u)
                depths[u] = depths[v] + 1
                if depths[u] > depths[mt2]:
                    mt2 = u
                vs.add(u)
                fs.add(u)
        else:
            pass
    r = max(depths[mt2], r)
print(r if r != inf else -1)

Submission status: Time Limit Exceeded

Solution code:
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    def match(self,s):
        n = len(s)
        j = 0
        ret = [0]*n
        for i in range(n):
            while j >= 0 and (j == self.n or s[i] != self.pattern[j]):
                j = self.ktable[j]
            j += 1
            if j == self.n:
                ret[(i-self.n+1)%n] = 1 
        return ret

def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    k = 1 - (-(m-1)//n)
    si = s*k
    a = KMP(t)
    b = a.match(si)
    edges = [[] for i in range(n)]
    indegree = [0] * n
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            edges[i].append(k)
            indegree[k] += 1
    
    def topSort():
        q = []
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)
        while q:
            cur = q.pop(0)
            res.append(cur)
            for nei in edges[cur]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)
        return len(res) == n
    
    res = []
    dp = [0] * n
    flag = topSort()
    if flag:
        for k in range(n):
            i = res[k]
            for j in edges[i]:
                dp[j] = max(dp[j], dp[i] + 1)
        ans = max(dp)
    else:
        ans = -1
    return ans
     

if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    i = 1
    lcp = 0
    while i < n:
        while i+lcp < n and s[i+lcp] == s[lcp]:
            lcp += 1
        z[i] = lcp

        if lcp == 0:
            i += 1
            continue

        k = 1
        while i+k < n and k+z[k] < lcp:
            z[i+k] = z[k]
            k += 1
        i += k
        lcp -= k

    return z

from collections import deque
def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res

import sys

def main():
    input = sys.stdin.readline
    s = input().rstrip()
    t = input().rstrip()

    n0 = len(s)
    m = len(t)

    s = s * (m // n0 + 2)

    idx = s.find(t)

    if idx >= 0:
        z = z_algorithm(s[idx:])
        # print(z)

        graph = [[] for _ in range(n0)]
        for i in range(n0):
            if i >= idx and z[i-idx] >= m:
                graph[i].append( (i + m) % n0 )

        ts = topological_sort(graph, n0)
        if len(ts) != n0:
            ans = -1
        else:
            # print(ts)
            ans = 0
            path = [0] * n0
            for i in range(n0):
                ans = max(ans, path[ts[i]])
                for j in graph[ts[i]]:
                    path[j] = path[ts[i]] + 1
    else:
        ans = 0

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    i = 1
    lcp = 0
    while i < n:
        while i+lcp < n and s[i+lcp] == s[lcp]:
            lcp += 1
        z[i] = lcp

        if lcp == 0:
            i += 1
            continue

        k = 1
        while i+k < n and k+z[k] < lcp:
            z[i+k] = z[k]
            k += 1
        i += k
        lcp -= k

    return z

from collections import deque
def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res

s = input()
t = input()

n0 = len(s)
m = len(t)

s = s * (m // n0 + 2)

idx = s.find(t)

if idx >= 0:
    z = z_algorithm(s[idx:])
    # print(z)

    graph = [[] for _ in range(n0)]
    for i in range(n0):
        if i >= idx and z[i-idx] >= m:
            graph[i].append( (i + m) % n0 )

    ts = topological_sort(graph, n0)
    if len(ts) != n0:
        ans = -1
    else:
        # print(ts)
        ans = 0
        path = [0] * n0
        for i in range(n0):
            ans = max(ans, path[ts[i]])
            for j in graph[ts[i]]:
                path[j] = path[ts[i]] + 1
else:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    i = 1
    lcp = 0
    while i < n:
        while i+lcp < n and s[i+lcp] == s[lcp]:
            lcp += 1
        z[i] = lcp

        if lcp == 0:
            i += 1
            continue

        k = 1
        while i+k < n and k+z[k] < lcp:
            z[i+k] = z[k]
            k += 1
        i += k
        lcp -= k

    return z

from collections import deque
def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res

s = input()
t = input()

n0 = len(s)
m = len(t)

s = s * ((n0 + m) // n0 + 1)

idx = s.find(t)

if idx >= 0:
    z = z_algorithm(s[idx:])
    # print(z)

    graph = [[] for _ in range(n0)]
    for i in range(n0):
        if i >= idx and z[i-idx] >= m:
            graph[i].append( (1, (i + m) % n0) )

    ts = topological_sort(graph, n0)
    if len(ts) != n0:
        ans = -1
    else:
        # print(ts)
        ans = 0
        path = [0] * n0
        for i in range(n0):
            ans = max(ans, path[ts[i]])
            for _, j in graph[ts[i]]:
                path[j] = path[ts[i]] + 1
else:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re

s = input()
t = input()

N = len(s)
M = len(t)

def matches(S, T, i):
    M = len(T)
    for j in range(len(T)):
        if S[(i + j) % N] != T[j]:
            return False
    return True

start = 0
i = 0
count = 0
ans = 0
breaks = set()
matches = [matches(s, t, i) for i in range(N)]
paths = [None for x in range(N)]
currentPath = []

# print(matches)
for i in range(N):
    start = i
    l = 0
    # print("Start", i)
    while matches[start]:
        # print(start)
        if start in currentPath:
            print(-1)
            exit(0)
        if paths[start] is not None:
            l += paths[start]
            break

        currentPath.append(start)
        l += 1
        start = (start + M) % N

    for j, x in enumerate(currentPath):
        paths[x] = l - j

    currentPath = []

paths = paths + [0]
# print(paths)
print(max(p for p in paths if p is not None))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
from scipy import signal

def solve(s: str, t: str):
    # 使われているアルファベット集合
    alpha = np.unique(list(s+t))
    a2i = {alpha: i for i, alpha in enumerate(alpha)}

    # s の長さが t の2倍になるように繰り返す。
    rep = (2*len(t)) // len(s) + 1
    s2 = s*rep

    # 畳み込み用の二次元配列とする。
    s_ary = np.zeros((len(s2), len(alpha)))
    t_ary = np.zeros((len(t), len(alpha)))
    for n, char in enumerate(s2):
        s_ary[n, a2i[char]] = 1.0
    for n, char in enumerate(t):
        t_ary[n, a2i[char]] = 1.0

    # FFT で畳み込みを計算
    convs = [np.round(signal.fftconvolve(s_ary[:,i], t_ary[::-1,i], mode="full")) for i in range(len(alpha))]
    conv = np.sum(convs, axis=0)[len(t)-1:len(t)+len(s)-1]

    # 部分文字列が一致するかのフラグ配列
    inc = (conv > (len(t) - 0.5))

    # print(inc)

    A = np.zeros(len(s), dtype=int)

    rst = 0
    for i in range(len(s)):
        j = i
        cnt = 0
        Aval = 0
        while inc[j]:
            # すでに来たことがある場合
            if A[j] > 0:
                Aval = A[j]
                break

            cnt += 1
            j = (j + len(t)) % len(s)

            # 無限ループを検知
            if i==j:
                print(-1)
                return

        j = i
        for k in range(cnt):
            A[j] = Aval + cnt - k
            j = (j + len(t)) % len(s)

        rst = max(A)

    print(rst)

        


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

word = [t,'?'] + [s]*(len(t)//len(s)+2)

z = Z(''.join(word))
z = z[len(t)+1:]

g = [-1]*len(s)
c = [0]*len(s)

for i in range(len(s)):
    if z[i] == len(t):
        g[i] = (i+len(t))%len(s)

for i in range(len(s)):
    if c[i] > 0 or g[i] < 0:
        continue
    q = g[i]
    tmp = 0
    while q >= 0:
        tmp += 1

        if c[q] > 0:
            c[i] = tmp + c[q]
            break
        
        if tmp != 0 and q == i:
            print(-1)
            exit()
        
        q = g[q]

    c[i] = max(c[i],tmp)

print(max(c))

Submission status: Time Limit Exceeded

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

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

z = Z(t+'?'+s*(len(t)//len(s) + 2))
z = z[len(t)+1:]

g = [-1]*len(s)
c = [0]*len(s)

for i in range(len(s)):
    if z[i] == len(t):
        g[i] = (i+len(t))%len(s)

for i in range(len(s)):
    if c[i] > 0 or g[i] < 0:
        continue
    q = g[i]
    tmp = 0
    while q >= 0:
        tmp += 1

        if c[q] > 0:
            c[i] = tmp + c[q]
            break
        
        if tmp != 0 and q == i:
            print(-1)
            exit()
        
        q = g[q]

    c[i] = max(c[i],tmp)

print(max(c))