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:
#参考:https://engineeringnote.hateblo.jp/entry/python/algorithm-and-data-structures/kmp_algorithm
from collections import deque
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table
 
def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    res=[]
    while i < len(string) and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j==M:
            res.append(i-j)
            j=0
    return res

s=input()
t=input()
N=len(s)
M=len(t)
k=-((-2*M)//N)+2
#print(s*k)
#print(t)
X=kmp_search(s*k,t)
#print(X)
G=[set() for i in range(N)]
for i in X:
    G[i%N].add((i+M)%N)
#print(G)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
#print(res)
if len(res)==0:
    print(-1)
    exit()
ans=[0 for i in range(N)]
for k in range(N-1,-1,-1):
    i=res[k]
    #print(ans)
    tmp=0
    for j in G[i]:
        tmp=max(ans[j],tmp)
    ans[i]=tmp+1
print(max(ans)-1)

Submission status: Runtime Error

Solution code:
def temp():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    if s == t:
        print("{}".format(-1))
        return
    if len(s) >= len(t):
        for i in range(int(ls/lt)+1, 1, -1):
            if t*i in 2*s:
                print("{}".format(i))
                return
    elif len(s) < len(t):
        if s*lt == t*ls:
            print("{}".format(-1))
            return
        if t in s*(int(lt/ls)+1):
            print("{}".format(1))
            return
    print("{}".format(0))

temp()

Submission status: Runtime Error

Solution code:
def temp():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    if len(s) > len(t):
        for i in range(int(ls/lt)+1, 1, -1):
            if t*i in 2*s:
                print("{}".format(i))
                return
    elif len(s) < len(t):
        if s*lt == t*ls:
            print("{}".format(-1))
            return
        if t in s*(int(lt/ls)+1):
            print("{}".format(1))
            return
    elif len(s) == len(t):
        if s == t:
            print("{}".format(-1))
            return
    print("{}".format(0))

temp()

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
flag = False

if len(s) > len(t):
    for i in range(int(ls/lt)+1, 1, -1):
        if t*i in 2*s:
            print("{}".format(i))
            flag = True
elif len(s) < len(t):
    if s*lt == t*ls:
        print("{}".format(-1))
        flag = True
    if t in s*(int(lt/ls)+1):
        print("{}".format(1))
        flag = True
elif len(s) == len(t):
    if s == t:
        print("{}".format(-1))
        flag = True
if not flag:
    print("{}".format(0))

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)

if len(s) > len(t):
    for i in range(int(ls/lt)+1, 1, -1):
        if t*i in 2*s:
            print("{}".format(i))
            return
elif len(s) < len(t):
    if s*lt == t*ls:
        print("{}".format(-1))
        return
    if t in s*(int(lt/ls)+1):
        print("{}".format(1))
        return
elif len(s) == len(t):
    if s == t:
        print("{}".format(-1))
        return
print("{}".format(0))

Submission status: Runtime Error

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1000
        self.mod1 = 10**9 + 7
        self.mod1 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = ((self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod1 + self.mod1) % self.mod1
        t2 = ((self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2 + self.mod2) % self.mod2
        return (t1, t2)

t_tmp = input().rstrip()
s = input().rstrip()

# Same character goes to infinity
if t_tmp.count(t_tmp[0]) == len(t_tmp) and s.count(s[0]) == len(s) and s[0] == t_tmp[0]:
    print(-1)
    exit()

t = ""
while len(t) < len(s):
    t += t_tmp
max_ans = (len(t) * 2) // len(s)
t = t * 3
lent = len(t)
lens = len(s)

RHt = RollingHash(t)
RHs = RollingHash(s)
s_hash = RHs.get(0, lens)

match = [0] * (lent - lens + 1)
for i in range(lent - lens + 1):
    if RHt.get(i, i+lens) == s_hash:
        match[i] = 1
ans = max(match[:lens])
for i in range(len(match) - lens):
    if match[i+lens] != 0:
        match[i+lens] += match[i]
        ans = max(ans, match[i+lens])

if ans > max_ans:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

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

def z_algorithm(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 j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

if len(s) == 1:
    aa = [0]
    print(a[1])
  
  
#sを伸ばす
new_s = s
while True:
    if len(new_s) > len(t):
        s = new_s
        break
    new_s += new_s

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)

Submission status: Runtime Error

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

def z_algorithm(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 j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = ""
while True:
    new_s += s
    if len(new_s) > len(t):
        s = new_s
        break
print(1)
exit()

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)
'''
print(ans1)

Submission status: Runtime Error

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

def z_algorithm(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 j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if visited[i]:
            break
        if i < 0 or len(li) <= i:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = ""
while True:
    new_s += s
    if len(new_s) > len(t):
        s = new_s
        break

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))
'''
s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)
'''
print(ans1)

Submission status: Runtime Error

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

def z_algorithm(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 j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

new_s = ""
while True:
    new_s += s
    if len(new_s) >= len(t):
        s = new_s
        break

def solve(i, li):
    ans = 0
    if i < 0 or len(li) <= i:
        return 0
    if visited[i]:
        return 0
    if li[i] >= len(t):
        visited[i] = True
        ans += 1 + solve(i+len(t), li)
    if li[i] < len(t):
        visited[i] = True
    return ans

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import Counter

sys.setrecursionlimit(10*6)
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


class UnionFind(object):
    """UnionFind木
    """

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    # Sの方が長くなるように
    if T > S:
        s *= int(math.ceil(T/S))

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    # UnionFindで最も大きなグループの節点数が答え
    uf = UnionFind(S)
    for i, m in enumerate(match):
        if m >= S:
            continue
        if uf.same(m, (m+T) % S):
            print(-1)
            return
        uf.unite(m, (m+T) % S)

    print(Counter([uf.root(i) for i in range(S)]).most_common(1)[0][1]-1)
    return


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

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10*6)
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


class Graph(object):
    # 無向グラフを仮定する。
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。

        self.E[始点]は、[終点, 重み]を要素としたリスト
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def tree_diameter(g):
    """木gの直径を求める
    """
    def visit(prev, v):
        """
        prev: 一つ手前の頂点
        v: 今の頂点
        """
        most_t, most_w = 0, 0   # 最も遠い頂点を控える
        for dst, weight in g.E[v]:  # 頂点vから伸びる枝の中で
            if dst == prev:        # 一つ手前のprevに伸びる枝を覗いて
                continue
            t, w = visit(v, dst)  # 再帰的に求める。返り値は最も遠い頂点とそこまでの距離
            w += weight           # 今の枝の距離を加えて
            if most_w < w:        # 遠さが更新されれば
                most_t, most_w = t, w  # 更新
        return most_t, most_w

    far_v, dist = visit(-1, 0)
    far_v, dist = visit(-1, far_v)
    return dist


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    # Sの方が長くなるように
    if T > S:
        s *= int(math.ceil(T/S))

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    print(-1)
    # g = Graph(S)
    # for m in match:
    #     g.add_edge([m % S, (m+T) % S])

    # d = tree_diameter(g)
    # print(d+1)

    return


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

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10*6)
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


class Graph(object):
    # 無向グラフを仮定する。
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。

        self.E[始点]は、[終点, 重み]を要素としたリスト
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def tree_diameter(g):
    """木gの直径を求める
    """
    def visit(prev, v):
        """
        prev: 一つ手前の頂点
        v: 今の頂点
        """
        most_t, most_w = 0, 0   # 最も遠い頂点を控える
        for dst, weight in g.E[v]:  # 頂点vから伸びる枝の中で
            if dst == prev:        # 一つ手前のprevに伸びる枝を覗いて
                continue
            t, w = visit(v, dst)  # 再帰的に求める。返り値は最も遠い頂点とそこまでの距離
            w += weight           # 今の枝の距離を加えて
            if most_w < w:        # 遠さが更新されれば
                most_t, most_w = t, w  # 更新
        return most_t, most_w

    far_v, dist = visit(-1, 0)
    far_v, dist = visit(-1, far_v)
    return dist


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    g = Graph(S)
    for m in match:
        g.add_edge([m % S, (m+T) % S])

    d = tree_diameter(g)
    print(d+1)

    return


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

Solution code:
from collections import defaultdict
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

s = input()
t = input()

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

class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

u = UnionFind(len(s))

for i in range(len(s)):
    j = (i+len(t)%len(s))
    if z[i] == len(t) and z[j] == len(t):
        u.union(i,j)

d = defaultdict(list)
for i in range(len(s)):
    if z[i] == len(t):
        d[u.find(i)].append(i)

ans = 0
INF = float('inf')
for k in d:
    i = d[k][0]
    j = i+len(t)*(len(d[k])-1)
    if z[j] == len(t) and i != j:
        ans = INF
    ans = max(ans,len(d[k]))
    
print(ans)

Submission status: Runtime Error

Solution code:
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

from collections import defaultdict
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]
        self.sz = defaultdict(lambda:1)

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)

        if s1 != s2:
            size = self.sz[s1]+self.sz[s2]
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            s = self.find(x)
            self.sz[s] = size
            return True
        return False

    def size(self, x):
        s = self.find(x)
        return self.sz[s]

from math import ceil

s = input()
t = input()

s = s*ceil(len(t)//len(s))*2

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

u = UnionFind(len(z)+len(t))
for i in range(len(z)-len(t)):
    if z[i]==len(t) and z[i+len(t)]==len(t):
        u.union(i,i+len(t))

ans = 0
for i in range(len(z)):
    if z[i] == len(t):
        ans = max(ans,u.sz[i])

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

for i in range(len(z)-len(t)*2,len(z)-len(t)):
    if z[i]==len(t) and z[i+len(t)]==len(t):
        u.union(i,i+len(t))

for i in range(len(z)):
    if z[i] == len(t):
        if ans < u.sz[i]:
            ans = -1

print(ans)

Submission status: Runtime Error

Solution code:
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

from collections import defaultdict
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]
        self.sz = defaultdict(lambda:1)

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)

        if s1 != s2:
            size = self.sz[s1]+self.sz[s2]
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            s = self.find(x)
            self.sz[s] = size
            return True
        return False

    def size(self, x):
        s = self.find(x)
        return self.sz[s]

from math import ceil

s = input()
t = input()

s = s*(ceil(len(t)//len(s)))*2

z = Z(t+'*'+s)
z = z[len(t)+1:]
u = UnionFind(len(z)+len(s))
for i in range(len(z)-len(t)):
    if z[i]==len(t) and z[i+len(t)]==len(t):
        u.union(i,i+len(t))

ans = 0
for i in range(len(z)):
    ans = max(u.sz[i],ans)


z = Z(t+'*'+s+s[:len(t)])
z = z[len(t)+1:]
for i in range(len(s)-len(t),len(z)-len(t)):
    if z[i]==len(t) and z[i+len(t)]==len(t):
        u.union(i,i+len(t))

for i in range(len(z)):
    if u.sz[i] > ans:
        ans = -1

if max(z) != len(t):
    ans = 0

print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N=1000000,M=500000;
int n,m;
char a[N+5],b[M+5];
struct _hash{
	int hbase1,hbase2,hmod1,hmod2;
	int pw1[N+1],Hsh1[N+1],pw2[N+1],Hsh2[N+1];
	void init(char str[],int len){
		hbase1=131;hbase2=13331;hmod1=1000000007;hmod2=998244353;
		pw1[0]=pw2[0]=1;
		for(int i=1;i<=len;i++)
			pw1[i]=1ll*pw1[i-1]*hbase1%hmod1,
			pw2[i]=1ll*pw2[i-1]*hbase2%hmod2,
			Hsh1[i]=(1ll*Hsh1[i-1]*hbase1+str[i])%hmod1,
			Hsh2[i]=(1ll*Hsh2[i-1]*hbase2+str[i])%hmod2;
	}
	pair<int,int> hsh(int l,int r){
		return mp((Hsh1[r]-1ll*Hsh1[l-1]*pw1[r-l+1]%hmod1+hmod1)%hmod1,(Hsh2[r]-1ll*Hsh2[l-1]*pw2[r-l+1]%hmod2+hmod2)%hmod2);
	}
}hsha,hshb;
bool ne1(int ra,int rb){
	for(int i=1;i<=ra;i++)if(hsha.hsh(i,i+ra-1)==hshb.hsh(1,rb))return true;
	return false;
}
bool mch[N+1],vis[N+1];
int main(){
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1);m=strlen(b+1);
	for(int i=1;i<=n;i++)a[i+n]=a[i];
	for(int i=1;i<=m;i++)b[i+m]=b[i];
	n<<=1;m<<=1;
	hsha.init(a,n);hshb.init(b,m);
	int ra,rb;
	for(int i=2;i<=(n>>1)+1;i++)if(hsha.hsh(1,n>>1)==hsha.hsh(i,i+(n>>1)-1)){ra=i-1;break;}
	for(int i=2;i<=(m>>1)+1;i++)if(hshb.hsh(1,n>>1)==hshb.hsh(i,i+(n>>1)-1)){rb=i-1;break;}
	if(ra==rb&&ne1(ra,rb))return puts("-1")&0;
	for(int i=1;i+(m>>1)-1<=n;i++)if(hsha.hsh(i,i+(m>>1)-1)==hshb.hsh(1,m>>1))mch[i]=true;
	int ans=0;
	for(int i=1;i<=n;i++)if(!vis[i]&&mch[i]){
		int now=i,cnt=1;
		while(now+(m>>1)<=n&&mch[now+(m>>1)])vis[now+=m>>1]=true,cnt++;
		ans=max(ans,cnt);
	}
	printf("%d",ans);
	return 0;
}
/*1
abcabab
ab
*/
/*2
aa
aaaaaaa
*/
/*3
aba
baaab
*/

Submission status: Runtime Error

Solution code:
def rolling_hash(s, w, MOD):
    ret = []
    tmp = 0
    p = pow(26, w, MOD)
    ords = [ord(c) - 97 for c in s]
    for i, o in enumerate(ords):
        tmp = tmp * 26 + o
        if i >= w:
            tmp = (tmp - ords[i - w] * p)
        tmp %= MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    k = (lt - 1) // ls + 1
    s *= k * 2
    ls *= k
    rs, rt = rolling_hash(s, lt, MOD), rolling_hash(t, lt, MOD)
    rs = rs[ls:]
    ht = rt[-1]

    checked = [-1] * ls

    def series(i, st):
        if i == st:
            return float('-inf')
        if checked[i] == -1:
            checked[i] = series((i + lt) % ls, st) + 1 if rs[i] == ht else 0
        return checked[i]

    for i, hs in enumerate(rs):
        if hs != ht:
            continue
        ret = series((i + lt) % ls, i)
        if ret == float('-inf'):
            return -1
        checked[i] = ret + 1

    return max(0, max(checked))


s = input()
t = input()
print(solve(s, t))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10*6)
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


class Graph(object):
    # 無向グラフを仮定する。
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。

        self.E[始点]は、[終点, 重み]を要素としたリスト
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def tree_diameter(g):
    """木gの直径を求める
    """
    def visit(prev, v):
        """
        prev: 一つ手前の頂点
        v: 今の頂点
        """
        most_t, most_w = 0, 0   # 最も遠い頂点を控える
        for dst, weight in g.E[v]:  # 頂点vから伸びる枝の中で
            if dst == prev:        # 一つ手前のprevに伸びる枝を覗いて
                continue
            t, w = visit(v, dst)  # 再帰的に求める。返り値は最も遠い頂点とそこまでの距離
            w += weight           # 今の枝の距離を加えて
            if most_w < w:        # 遠さが更新されれば
                most_t, most_w = t, w  # 更新
        return most_t, most_w

    far_v, dist = visit(-1, 0)
    far_v, dist = visit(-1, far_v)
    return dist


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    LCM = S*T//GCD(S, T)
    if s*(LCM//S) == t*(LCM//T):
        print(s*(LCM//S))
        print(-1)
        return

    print(-1)

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    g = Graph(S)
    for m in match:
        g.add_edge([m % S, (m+T) % S])

    d = tree_diameter(g)
    print(d+1)

    return


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()