Problem p02962 (python)

Fixed submission:

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)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y]+=self.size[x]
        else:
            self.parent[y] = x
            self.size[x]+=self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
      
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
U = UnionFind(ls)
for i in range(ls):
    if is_same[i]:
        if U.same(i, (i+k)%ls):
            ans = -1
            break
        U.unite(i, (i+k)%ls)
if ans == -1:
    print(-1)
else:
    ans = max(U.get_size(i)-1 for i in range(ls))
    print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
ans = 0
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)