Problem: 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.

Submission attempts (in order):
from fractions import gcd


def larger_divisor(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            ret.add(n // i)
    return sorted(ret)


def solve(s, t):
    ls, lt = len(s), len(t)
    for d in larger_divisor(gcd(ls, lt)):
        unit = s[:d]
        if all(s[i:i + d] == unit for i in range(d, ls, d)) and all(t[i:i + d] == unit for i in range(0, lt, d)):
            return -1

    if ls < lt:
        k = (lt - 1) // ls + 1
        s *= k
    s *= 2
    ss = s.split(t)
    c = -1
    ans = 0
    for sp in ss:
        if sp == '':
            c += 1
        else:
            ans = max(ans, c + 1)
            c = 0
    ans = max(ans, c)
    return ans


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


from fractions import gcd


def larger_divisor(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            ret.add(n // i)
    return sorted(ret)


def rolling_hash(s, MASK):
    ret = []
    tmp = 0
    for c in s:
        tmp = (tmp * 26 + ord(c) - 97) & MASK
        ret.append(tmp)
    return ret


def solve(s, t):
    MASK = (1 << 63) - 1
    ls, lt = len(s), len(t)
    rs, rt = rolling_hash(s, MASK), rolling_hash(t, MASK)
    rt.append(0)
    for g in larger_divisor(gcd(ls, lt)):
        u = rs[g - 1]
        p = pow(26, g, MASK + 1)
        if all((rs[i + g - 1] - rs[i - 1] * p) & MASK == u for i in range(g, ls, g)) \
                and all((rt[i + g - 1] - rt[i - 1] * p) & MASK == u for i in range(0, lt, g)):
            return -1

    se = s
    if ls < lt:
        k = (lt - 1) // ls + 1
        se *= k
    se *= 3
    ss = se.split(t)

    if len(ss) == 1:
        return 0

    if ss[0] != '' and ss[-1] != '' and all(sc == '' for sc in ss[1:-1]):
        return solve(s[len(ss[0]):] + s[:len(ss[0])], t)

    c = -1
    ans = 0
    for sp in ss:
        if sp == '':
            c += 1
        else:
            ans = max(ans, c + 1)
            c = 0
    ans = max(ans, c)
    return ans


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


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):
        print(i, st, checked)
        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))


from fractions import gcd


def divisor(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
    return sorted(ret)


def solve(s, t):
    if all(c == s[0] for c in s) and all(c == s[0] for c in t):
        return -1

    ls, lt = len(s), len(t)
    for d in divisor(gcd(ls, lt)):
        unit = s[:d]
        if all(s[i:i + d] == unit for i in range(d, ls, d)) and all(t[i:i + d] == unit for i in range(0, lt, d)):
            return -1

    if ls < lt:
        k = (lt - 1) // ls + 1
        s *= k
    s *= 2
    ss = s.split(t)
    c = -1
    ans = 0
    for sp in ss:
        if sp == '':
            c += 1
        else:
            ans = max(ans, c + 1)
            c = 0
    ans = max(ans, c)
    return ans


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


from fractions import gcd


def larger_divisor(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            ret.add(n // i)
    return sorted(ret)


def rolling_hash(s, MASK):
    ret = []
    tmp = 0
    for c in s:
        tmp = (tmp * 26 + ord(c) - 97) & MASK
        ret.append(tmp)
    return ret


def solve(s, t):
    MASK = (1 << 63) - 1
    ls, lt = len(s), len(t)
    rs, rt = rolling_hash(s, MASK), rolling_hash(t, MASK)
    rt.append(0)
    for g in larger_divisor(gcd(ls, lt)):
        u = rs[g - 1]
        p = pow(26, g, MASK + 1)
        if all((rs[i + g - 1] - rs[i - 1] * p) & MASK == u for i in range(g, ls, g)) \
                and all((rt[i + g - 1] - rt[i - 1] * p) & MASK == u for i in range(0, lt, g)):
            return -1

    if ls < lt:
        k = (lt - 1) // ls + 1
        s *= k
    s *= 2
    ss = s.split(t)

    if len(ss) == 1:
        return 0

    if ss[0] != '' and ss[-1] != '' and all(sc == '' for sc in ss[1:-1]):
        return solve(s[len(ss[0]):] + s[:len(ss[0])], t)

    c = -1
    ans = 0
    for sp in ss:
        if sp == '':
            c += 1
        else:
            ans = max(ans, c + 1)
            c = 0
    ans = max(ans, c)
    return ans


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


from fractions import gcd


def larger_divisor(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            ret.add(n // i)
    return sorted(ret)


def rolling_hash(s, MOD):
    ret = []
    tmp = 0
    for c in s:
        tmp = (tmp * 26 + ord(c) - 97) % MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    rs, rt = rolling_hash(s, MOD), rolling_hash(t, MOD)
    rt.append(0)
    for g in larger_divisor(gcd(ls, lt)):
        u = rs[g - 1]
        p = pow(26, g, MOD)
        if all((rs[i + g - 1] - rs[i - 1] * p) % MOD == u for i in range(g, ls, g)) \
                and all((rt[i + g - 1] - rt[i - 1] * p) % MOD == u for i in range(0, lt, g)):
            return -1

    if ls < lt:
        k = (lt - 1) // ls + 1
        s *= k
    s *= 2
    ss = s.split(t)

    if len(ss) == 1:
        return 0

    if ss[0] != '' and ss[-1] != '' and all(sc == '' for sc in ss[1:-1]):
        return solve(s[len(ss[0]):] + s[:len(ss[0])], t)

    c = -1
    ans = 0
    for sp in ss:
        if sp == '':
            c += 1
        else:
            ans = max(ans, c + 1)
            c = 0
    ans = max(ans, c)
    return ans


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


import sys

sys.setrecursionlimit(10 ** 6)


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 st <= i < st + lt:
            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))


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted