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: Runtime Error

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=None):
        m1=self.__mod1; m2=self.__mod2
        if(r is None): r=self.__n
        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)
    if(n<m*5):
        s=s*ceil(5*m/n)

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

Submission status: Runtime Error

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=None):
        m1=self.__mod1; m2=self.__mod2
        if(r is None): r=self.__n
        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)
    if(n<m*4):
        s=s*ceil(4*m/n)

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

Submission status: Runtime Error

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):
    from random import randint
    __MASK30=(1<<30)-1
    __MASK31=(1<<31)-1
    __MOD=(1<<61)-1
    __base=randint(129,__MASK31)

    def __init__(self,s:str):
        n=len(s)
        H=[0]*(n+1); P=[1]*(n+1)
        for i in range(n):
            H[i+1]=self.__modulo(self.__multiple(H[i],self.__base)+ord(s[i]))
            P[i+1]=self.__modulo(self.__multiple(P[i],self.__base))
        self.__H=H; self.__P=P

    def __multiple(self,a,b):
        au=a>>31
        ad=a&self.__MASK31
        bu=b>>31
        bd=b&self.__MASK31
        m=ad*bu+au*bd
        mu=m>>30
        md=m&self.__MASK30
        return 2*au*bu+mu+(md<<31)+ad*bd

    def __modulo(self,x):
        x=(x&self.__MOD)+(x>>61)
        if(x>self.__MOD): x-=self.__MOD
        return x

    def hash(self,l,r):
        H=self.__H; P=self.__P
        res=H[r]+self.__MOD*3-self.__multiple(H[l],P[r-l])
        if(res<0): return res+self.__MOD
        else: return self.__modulo(res)

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

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

Submission status: Runtime Error

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 = 10**6 + 100
base = 1234
MOD = 10**9 + 9
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]
x[1:] -= Sext_hash[:LS-1]
x *= power_inv[:LS]; x %= MOD

Submission status: Runtime Error

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 = 10**6 + 100
base = 1234
MOD = 10**9 + 9
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]
x[1:] -= Sext_hash[:LS-1]
x *= power_inv[:LS]; x %= MOD

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

answer = max(cnt)
print(answer)

Submission status: Runtime Error

Solution code:
from math import *
from fractions import *
s=raw_input()
t=raw_input()
srep=s*(10**6)
trep=t*(10**6)
ans=0
def cmp(s,t):
	for i in range(min(len(s),len(t))):
		if s[i]!=t[i]:
			return i
	return min(len(s),len(t))
for i in range(len(s)):
	ans=max(ans,cmp(srep[i:],trep))
if ans<=5*10**5:
	print(ans/len(t))
else:
	print(-1)

Submission status: Runtime Error

Solution code:
from math import *
from fractions import *
s=raw_input()
t=raw_input()
srep=s*(1+len(t)/gcd(len(s),len(t)))
trep=t*(1+len(s)/gcd(len(s),len(t)))
ans=0
def cmp(s,t):
	for i in range(min(len(s),len(t))):
		if s[i]!=t[i]:
			return i
	return min(len(s),len(t))
for i in range(len(s)):
	ans=max(ans,cmp(srep[i:],trep))
ans/=len(t)
if ans<=5*10**5:
	print(ans)
else:
	print(-1)

Submission status: Runtime Error

Solution code:
from math import *
from fractions import *
s=raw_input()
t=raw_input()
srep=s*(1+len(t)/gcd(len(s),len(t)))
trep=t*(1+len(s)/gcd(len(s),len(t)))
ans=0
def cmp(s,t):
	for i in range(min(len(s),len(t))):
		if s[i]!=t[i]:
			return i
	return min(len(s),len(t))
for i in range(len(s)):
	ans=max(ans,cmp(srep[i:],trep))
ans/=len(t)
if ans<=10**5:
	print(ans)
else:
	print(-1)

Submission status: Runtime Error

Solution code:
s=raw_input()
t=raw_input()
srep=s*(len(t)/gcd(len(s),lent(t)))
trep=t*(len(s)/gcd(len(s),lent(t)))
ans=0
def cmp(s,t):
	for i in range(min(len(s),len(t))):
		if s[i]!=t[i]:
			return i
	return min(len(s),len(t))
for i in range(len(s)):
	ans=max(ans,cmp(srep[i:],trep))
ans/=len(t)
if ans<=10**5:
	print(ans)
else:
	print(-1)

Submission status: Runtime Error

Solution code:
s=raw_input()
t=raw_input()
srep=s*(10**6)
trep=t*(10**6)
ans=0
def cmp(s,t):
	for i in range(min(len(s),len(t))):
		if s[i]!=t[i]:
			return i
	return min(len(s),len(t))
for i in range(len(s)):
	ans=max(ans,cmp(srep[i:],trep))
ans/=len(t)
if ans<=10**5:
	print(ans)
else:
	print(-1)

Submission status: Runtime Error

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)
    
    graph = [[] for i in range(n)]
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            graph[i].append(k)
    
    def dfs(node):
        if visited[node] == 1: return True
        if visited[node] == 2: return False

        visited[node] = 1
        for nei in graph[node]:
            if dfs(nei): return True
        visited[node] = 2
        res.append(node)
        return False

    visited = [0] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    
    res = res[::-1]
    dp = [0] * n

    for k in range(n):
        i = res[k]
        for j in graph[i]:
            dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

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

Submission status: Runtime Error

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)
    
    graph = [[] for i in range(n)]
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            graph[i].append(k)
    
    def dfs(node):
        if visited[node] == 1: return True
        if visited[node] == 2: return False

        visited[node] = 1
        for nei in graph[node]:
            if dfs(nei): return True
        visited[node] = 2
        res.append(node)
        return False

    visited = [0] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    
    res = res[::-1]
    dp = [0] * n

    for k in range(n):
        i = res[k]
        for j in graph[i]:
            dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

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

Submission status: Runtime Error

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)
    
    graph = collections.defaultdict(set)
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            graph[i].append(k)
    
    def dfs(node):
        if visited[node] == 1: return True
        if visited[node] == 2: return False

        visited[node] = 1
        for nei in graph[node]:
            if dfs(nei): return True
        visited[node] = 2
        res.append(node)
        return False

    visited = [0] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    
    res = res[::-1]
    dp = [0] * n

    for k in range(n):
        i = res[k]
        for j in graph[i]:
            dp[j] = max(dp[j], dp[i] + 1)
            ans = max(dp)
    return ans

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

Submission status: Runtime Error

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 = collections.deque()
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)
        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: Runtime Error

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 dfs1(node):
        if visited[node] == 1:
            return True
        if visited[node] == 2:
            return False
        visited[node] = 1
        for nei in edges[node]:
            if dfs1(nei):
                return True
        visited[node] = 2
        return False
    visited = [-1] * n
    for i in range(n):
        if dfs1(i):
            return -1
    
    
    
    def dfs(node, adj, dp, vis):  
        
        vis[node] = True  
        for i in range(0, len(adj[node])):   
            if not vis[adj[node][i]]: 
                dfs(adj[node][i], adj, dp, vis)   
            dp[node] = max(dp[node], 1 + dp[adj[node][i]])   
         
    def findLongestPath(adj, n):  
    
        dp = [0] * n 
          
        vis = [False] * n
     
        for i in range(n):   
            if not vis[i]:  
                dfs(i, adj, dp, vis) 
                
        ans = 0 
        for i in range(n):   
            ans = max(ans, dp[i])  
           
        return ans
    
    ans = findLongestPath(edges, n)
    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: Runtime Error

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
    
    res = res[::-1]
    dp = [0] * n
    ans = 0
    for i in range(n):
        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: Runtime Error

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: Runtime Error

Solution code:
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_table()

    def create_table(self):
        table = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = table[j]
            j += 1
            table[i+1] = j
        self.table = table

    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.table[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)
    #print a, b
    edges = [[] for i in range(n)]
    for i in range(n):
        if b[i]:
            edges[i].append((i+m)%n)
    #print 'edges', edges
    visited = [0]*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
    
    res = []
    for i in range(n):
        if dfs(i):
            print(-1)
            break
    else:
        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])
        print(ans)

if __name__ == "__main__":
    main()