Problem p02962 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
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]


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

    # グラフを構成し、最長パスが答え。ループがあれば-1
    # グラフは辞書で表現
    edges = {}
    rev_edges = {}
    for i, m in enumerate(match):
        if m >= S:
            continue
        edges[m] = (m+T) % S
        rev_edges[(m+T) % S] = m

    # 何度も同じ経路を確認するのを改善しうる
    maxlenpath = 1
    visitted = defaultdict(int)
    for k in edges:
        # kが含まれるパスを考える。
        # 逆向きにはったグラフを利用して、双方向の長さを求める
        if visitted[k]:
            continue
        counter = 0
        b = k
        while b in edges:
            counter += 1
            b = edges[b]
            if visitted[b]:
                print(-1)
                return
            else:
                visitted[b] = 1
        b = k
        while b in rev_edges:
            counter += 1
            b = rev_edges[b]
            if visitted[b]:
                print(-1)
                return
            else:
                visitted[b] = 1
        # print("visitted: ", visitted)
        # print("counter: ", counter)
        if maxlenpath < counter:
            maxlenpath = counter
    print(maxlenpath)
    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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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(-1)
        return

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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
INF = float("inf")


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


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

    # Zアルゴリズムなどを陽に使わなくとも、findでいけるか？
    s2 = s+s
    match = []
    pos = s2.find(t, 0)
    while 0 <= pos < S:
        match.append(pos)
        pos = s2.find(t, pos+1)

    if len(match) == 0:
        # とも限らないけどなー。
        # s = "ABC"
        # t = "ABCABCABC"
        # でもこれなら無限か
        print(0)
        return

    g = Graph(S)
    for m in match:
        g.add_edge([m, (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()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


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


def solve(s: str, t: str):
    S = len(s)
    T = len(t)
    scf = S*T//GCD(S, T)
    if s*(scf//S) == t*(scf//T):
        print(-1)
        return

    J = max(-(-2*T//S), 2)
    mi = 0
    SJ = s*J

    mi = 0
    curr = 0
    cand = [1]

    while True:
        counter = 0
        pos = SJ.find(t, curr)
        while pos >= 0:
            counter += 1
            if SJ[pos:].startswith(t):
                pos += len(t)
            else:
                break
        cand.append(counter)
        curr = pos
        if curr < 0 or curr > len(SJ):
            break
    print(max(cand)-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()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


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


def solve(s: str, t: str):
    S = len(s)
    T = len(t)
    scf = S*T//GCD(S, T)
    if s*(scf//S) == t*(scf//T):
        print(-1)
        return

    J = max(-(-2*T//S), 2)
    mi = 0
    SJ = s*J

    a = list(range(S*J//T))

    def isOK(index, key):
        return t*a[index] not in key

    def binary_search(key):
        ng = -1
        ok = len(a)

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    print(binary_search(SJ)-1)

    # print(mi)

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