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: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        haystack の何番目に needle があるか。見つからなければ -1
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i = self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


def test(t, s):
    ret = []
    for i in range(len(s)):
        ret.append(s[i:i + len(t)] == t)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

# kmp = KMP(T)
# print(kmp.search(S))

S *= 4
while len(S) < len(T) * 4:
    S *= 2

kmp = KMP(T)
idx = kmp.search(S)
ans = 0
for k in range(len(T)):
    i = k
    cnt = 0
    while i < len(idx):
        if idx[i]:
            cnt += 1
        else:
            ans = max(cnt, ans)
            cnt = 0
        i += len(T)
    ans = max(cnt, ans)
if len(T) * ans >= len(S) // 4 * 3:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		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 not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

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

Submission status: Accepted

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 = set()
for a, b in kmp_search(m*s, t):
    d.add(a%len(s))

d2 = set()
for i in range(len(s)):
    if i not in d:
        d2.add(i)
q = d2

LT, LS = len(t), len(s)
dist = [inf] * LS
d = 0
while q:
    qq = []
    for x in q:
        if dist[x] == inf:
            dist[x] = d
            qq.append((x-LT)%LS)
    d += 1
    q = qq

answer = max(dist)
if answer >= inf:
    answer = -1

print(answer)

Submission status: Accepted

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 = [-1]*(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 ls[i] != -1:
            c += ls[i]
            break
    if c == inf:
        break
    ls[j] = c
print(max(ls) if c != inf else -1)

Submission status: Accepted

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)
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 = dict()
    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 = dict()
    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: Accepted

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 = dict()
    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 = dict()
    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: Accepted

Solution code:

def search_rolling_hash(S, T):
    base = 1234
    mod = 2**64-1
    n, m = len(S), len(T)
    rolling_hash = [0]*(n-m+1)  
    rolling_hash[0] = ord(S[0])
    b_m = pow(base, m, mod)
    T_hash = ord(T[0])
    start_index = []
    for i in range(1, m):
        rolling_hash[0]*=base
        rolling_hash[0]+=ord(S[i])
        rolling_hash[0]%=mod
        T_hash = (T_hash*base+ord(T[i]))%mod
    if rolling_hash[0] == T_hash: start_index.append(0)
    for i in range(1, ls):
        rolling_hash[i] = (rolling_hash[i-1]*base-ord(S[i-1])*b_m+ord(S[i+m-1]))%mod
        if rolling_hash[i] == T_hash: start_index.append(i)
    return start_index
import sys
s = input()
t = input()
ls, lt = len(s), len(t)
S = s*(lt//ls+2)
index = search_rolling_hash(S, t)
flag = [False]*ls
for i in index:
    flag[i] = True
stack = []
inf = float('inf')
cnt = [inf]*ls
for i in range(ls):
    if flag[i] == False:
        stack.append(i)
        cnt[i] = 0
while stack:
    x = stack.pop()
    y = (x-lt)%ls
    if cnt[y] == inf:
        cnt[y] = cnt[x]+1
        stack.append(y)
ans = max(cnt)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:

def search_rolling_hash(S, T):
    base = 1234
    mod = 10**9+7
    n, m = len(S), len(T)
    rolling_hash = [0]*(n-m+1)  
    rolling_hash[0] = ord(S[0])
    b_m = pow(base, m, mod)
    T_hash = ord(T[0])
    start_index = []
    for i in range(1, m):
        rolling_hash[0]*=base
        rolling_hash[0]+=ord(S[i])
        rolling_hash[0]%=mod
        T_hash = (T_hash*base+ord(T[i]))%mod
    if rolling_hash[0] == T_hash: start_index.append(0)
    for i in range(1, ls):
        rolling_hash[i] = (rolling_hash[i-1]*base-ord(S[i-1])*b_m+ord(S[i+m-1]))%mod
        if rolling_hash[i] == T_hash: start_index.append(i)
    return start_index
import sys
s = input()
t = input()
ls, lt = len(s), len(t)
S = s*(lt//ls+2)
index = search_rolling_hash(S, t)
flag = [False]*ls
for i in index:
    flag[i] = True
stack = []
inf = float('inf')
cnt = [inf]*ls
for i in range(ls):
    if flag[i] == False:
        stack.append(i)
        cnt[i] = 0
while stack:
    x = stack.pop()
    y = (x-lt)%ls
    if cnt[y] == inf:
        cnt[y] = cnt[x]+1
        stack.append(y)
ans = max(cnt)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        n=len(s)
        self.__s=s
        self.__n=n
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(n+1),[0]*(n+1)
        P1,P2=[1]*(n+1),[1]*(n+1)
        for i in range(n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def hash(self,l,r):
        m1=self.__mod1; m2=self.__mod2
        assert 0<=l<=r<=self.__n
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)

def resolve():
    from math import ceil
    s=input()
    t=input()
    n=len(s)
    m=len(t)
    s=s*ceil(m/n)
    s=s*2

    ok=[0]*n
    uf=UnionFind(n)
    rhs=RollingHash(s)
    rht=RollingHash(t)
    t=rht.hash(0,m)
    for i in range(n):
        if(rhs.hash(i,i+m)==t):
            ok[i]=1
    for i in range(n):
        if(ok[i] and ok[(i+m)%n]):
            if(not uf.unite(i,(i+m)%n)):
                print(-1)
                return
    ans=0
    for i in range(n):
        if(ok[i]): ans=max(ans,uf.size(i))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

S = np.array(list(readline().rstrip()),np.int64)
T = np.array(list(readline().rstrip()),np.int64)

LS = len(S); LT = len(T)
LSext = LS + LT
LSext += (-LSext) % LS
Sext = np.tile(S,LSext//LS)

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 2*10**6
MOD = 10 ** 9 + 993
base = 123450
x = np.full(U,base,dtype=np.int64); x[0] = 1
power = cumprod(x,MOD)
x = np.full(U,pow(base,MOD-2,MOD),dtype=np.int64); x[0] = 1
power_inv = cumprod(x,MOD)

def RollingHash(S):
    return (S * power[:len(S)] % MOD).cumsum() % MOD

Sext_hash = RollingHash(Sext)
T_hash = RollingHash(T)[-1]

# ある地点を開始位置として、長さLTの文字列のhash値
x = Sext_hash[LT-1:LS+LT-1].copy()
x[1:] -= Sext_hash[:LS-1]
x *= power_inv[:LS]; x %= MOD

# ある場所から始めたとして、Tを繰り返せる回数
INF = LS+100
cnt = [INF] * LS
stack = np.where(x!=T_hash)[0].tolist()
for x in stack:
    cnt[x] = 0
while stack:
    x = stack.pop()
    y = (x-LT)%LS
    if cnt[y] == INF:
        cnt[y] = cnt[x] + 1
        stack.append(y)

answer = max(cnt)
if answer == INF:
    answer = -1
print(answer)

Submission status: Accepted

Solution code:
import collections
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)
    while len(s) < m + n:
        s += s
    a = KMP(t)
    b = a.match(s)
    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 = collections.deque([i for i in range(n) if indegree[i] == 0])
        while q:
            cur = q.popleft()
            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: Accepted

Solution code:
import collections
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 = collections.deque([i for i in range(n) if indegree[i] == 0])
        while q:
            cur = q.popleft()
            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: Accepted

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)]
#    for i in range(n):
#        if b[i]:
#            edges[i].append((i+m)%n)
#    
#    def dfs(node):
#        if visited[node] == 1:
#            return True
#        if visited[node] == 2:
#            return False
#        visited[node] = 1
#        for nei in edges[node]:
#            if dfs(nei):
#                return True
#        visited[node] = 2
#        res.append(node)
#        return False
#    visited = [-1] * n
#    res = []
#    for i in range(n):
#        if dfs(i):
#            return -1
#    dp = [0] * n
#    ans = 0
#    for i in range(n-1, -1, -1):
#        t = res[i]
#        for c in edges[t]:
#            dp[c] = max(dp[c], dp[t] + 1)
#            ans = max(ans, dp[c])
#    return ans

            
    visited = [0]*n
    loop = False
    ans = 0
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = 1
        cur = i
        right = 0
        while b[cur]:
            nxt = (cur + m) % n
            if visited[nxt]:
                loop = True
                break
            visited[nxt] = 1
            cur = nxt
            right += 1
        cur = i
        left = 0
        while b[(cur-m)%n]:
            nxt = (cur-m) % n
            if visited[nxt]:
                loop = True
                break
            visited[nxt] = 1
            cur = nxt
            left += 1
        if not loop:
            ans = max(ans, right+left)
        else:
            ans = -1
            break
    return ans

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

Submission status: Accepted

Solution code:
def getTableMP(Ss):
    lenS = len(Ss)
    table = [-1] * (lenS+1)
    j = -1
    for i in range(lenS):
        while j >= 0 and Ss[i] != Ss[j]:
            j = table[j]
        j += 1
        table[i+1] = j
    return table


Ss = input()
Ts = input()

lenS, lenT = len(Ss), len(Ts)
num = (lenT+lenS-1+lenS-1)//lenS
S2s = Ss * num

tableMP = getTableMP(Ts + '$' + S2s)

isFounds = [False] * lenS
for i in range(2*lenT+1, 2*lenT+lenS+1):
    if tableMP[i] >= lenT:
        isFounds[i-2*lenT-1] = True

ans = 0
numDone = 0
for i in range(lenS):
    if not isFounds[i]:
        i = (i+lenT)%lenS
        for num in range(lenS+1):
            if not isFounds[i]:
                ans = max(ans, num)
                numDone += num+1
                break
            i = (i+lenT)%lenS
        else:
            ans = -1
            break

if numDone < lenS:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
def getTableKMP(Ss):
    Ss += '$'
    lenS = len(Ss)
    table = [-1] * lenS
    j = -1
    for i in range(lenS-1):
        while j >= 0 and Ss[i] != Ss[j]:
            j = table[j]
        j += 1
        if Ss[i+1] == Ss[j]:
            table[i+1] = table[j]
        else:
            table[i+1] = j
    return table

def getPosPtnsKMP(Ss, ptn, table):
    anss = []
    lenS, lenP = len(Ss), len(ptn)
    iS, iP = 0, 0
    while iS < lenS:
        if Ss[iS] == ptn[iP]:
            iS += 1
            iP += 1
            if iP == lenP:
                anss.append(iS-lenP)
                iP = table[iP]
        else:
            iP = table[iP]
            if iP == -1:
                iS += 1
                iP = 0
    return anss


Ss = input()
Ts = input()

lenS, lenT = len(Ss), len(Ts)
num = (lenT+lenS-1+lenS-1) // lenS
S2s = Ss * num

tableKMP = getTableKMP(Ts)
posPtns = getPosPtnsKMP(S2s, Ts, tableKMP)

isFounds = [False] * lenS
for pos in posPtns:
    if pos >= lenS:
        break
    isFounds[pos] = True

ans = 0
numDone = 0
for i in range(lenS):
    if not isFounds[i]:
        i = (i+lenT) % lenS
        for num in range(lenS+1):
            if not isFounds[i]:
                ans = max(ans, num)
                numDone += num+1
                break
            i = (i+lenT) % lenS
        else:
            ans = -1
            break

if numDone < lenS:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def is_same(self, x, y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]



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



s = S()
t = S()
s_len= len(s)
t_len = len(t)
if s_len < t_len:
    s *= (t_len // s_len + 1)
s *= 2


A = z_algorithm(t + '?' + s)[t_len + 1: ]
graph = [[] for _ in range(s_len)]
U = UnionFind(s_len)

flag = False
for i in range(s_len):
    if A[i] == t_len:
        if U.is_same(i, (i + t_len) % s_len):
            flag = True
            break
        U.unite(i, (i + t_len) % s_len)


if flag:
    print(-1)
else:
    print(max(U.size) - 1)