Problem p02962 (python)

Fixed submission:
import sys
input = sys.stdin.readline
S = input().rstrip()
T = input().rstrip()

def z_algorithm(s):
    N = len(s)
    ret = [0]*N
    ret[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + ret[k]<j:
            ret[i+k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

def solve():
    ls,lt = len(S),len(T)
    ns = 0--(lt+ls)//ls

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

    from fractions import gcd
    g = gcd(ls,lt)
    uf = UnionFind(ls)
    match = False
    for i in range(ls):
        if za[lt+1+i] == lt:
            match = True
            j = (i+lt) % ls
            if uf.is_same(i,j):
                if uf.size(i) == ls//g:
                    print(-1)
                    exit()
                continue
            uf.unite(i,j)
    if not match:
        print(0)
        exit()

    ans = 0
    for i in range(ls):
        ans = max(ans, uf.size(i)-1)
    print(ans)

solve()

Buggy submission (verdict: Runtime Error):
S = input()
T = input()
ls,lt = len(S),len(T)
ns = 0--(lt+ls)//ls

def z_algorithm(s):
    N = len(s)
    ret = [0]*N
    ret[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + ret[k]<j:
            ret[i+k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

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

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

Buggy submission (verdict: Runtime Error):
S = input()
T = input()

if len(set(S))==1 and len(set(T))==1:
    print(-1)
    exit()
if len(T)%len(S) == 0:
    if S in T:
        i = T.index(S)
        TT = T + T
        for j in range(len(T)//len(S)):
            if TT[i+(j+1)*len(S):i+(j+2)*len(S)] != S:
                break
        else:
            print(-1)
            exit()
if len(S)%len(T) == 0:
    if T in S:
        i = S.index(T)
        SS = S + S
        for j in range(len(S)//len(T)):
            if SS[i+(j+1)*len(T):i+(j+2)*len(T)] != T:
                break
        else:
            print(-1)
            exit()

A = S * (1234567 // len(S))
assert len(A) > len(T)*2

if T not in A:
    print(0)
    exit()

i = seq = ans = 0
for a in A:
    if a == T[i]:
        i += 1
        if i==len(T):
            seq += 1
            ans = max(ans, seq)
            i = 0
    else:
        i = seq = 0
print(ans)