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: Wrong Answer

Solution code:
S = input()
W = input()
S *= 6


N = len(W)
p = min([1]+[i for i in range(1, N+1) if N%i == 0 and W[:-i] == W[i:]])
d = N//p
W = W[:d]

T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
f = 1
while i < len(S):
    k = KMP(i)
    if k == len(S):
        f = 0
        break
    elif k == 0:
        c += 1
    else:
        if c:
            f = 0
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if f:
    print(-1)
else:
    print(cmax//p)

Submission status: Wrong Answer

Solution code:
S = input()
W = input()
S *= 6


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
p = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        p = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    # print("i =", i)
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3 > len(S) * 2:
    print(-1)
else:
    print(cmax//p)

Submission status: Wrong Answer

Solution code:
S = input()
W = input()
S *= 6


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
p = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        p = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3 * p > len(S) * 2:
    print(-1)
else:
    print(cmax//p)

Submission status: Wrong Answer

Solution code:
S = input()
W = input()
S *= 6


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
p = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        p = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3> len(S) * 2:
    print(-1)
else:
    print(cmax//p)

Submission status: Wrong Answer

Solution code:
S = input()
W = input()
S *= 6


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
k = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        k = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3> len(S) * 2:
    print(-1)
else:
    print(cmax)

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
S = input()
W = input()
S *= 6

T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3> len(S) * 2:
    print(-1)
else:
    print(cmax)

Submission status: Wrong Answer

Solution code:
S = input()
W = input()
S *= 3

T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    k = KMP(i)
    if k == len(S):
        break
    elif k == 0:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + len(W)
if cmax * len(W) * 3 > len(S) * 2:
    print(-1)
else:
    print(cmax)

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def pi(s):
    p = [0] * len(s)
    for i in range(1, len(s)):
        g = p[i - 1]
        while g and (s[i] != s[g]):
            g = p[g - 1]
        p[i] = g + int(s[i] == s[g])

    return p


def match(s, pat):
    res = []
    p = pi(pat + '\0' + s)
    for i in range(len(p) - len(s), len(p)):
        if p[i] == len(pat):
            res.append(i - 2 * len(pat))

    return res


def main():
    s = input()
    t = input()

    n = len(s)
    s *= (len(t) + 2 * len(s) - 1) // len(s)

    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if not match(s, u):
            hi = mi
        else:
            lo = mi + 1

    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return

    print(lo - 1)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = 0
ans_ = 0
if len(s)>=len(t):
    S = s+s[-len(t):]
    S = S.replace(t,'*')
    c = 0
    for i in range(len(s)):
        if s[i]=='*':
            c += 1
            ans = max(ans,c)
        else:
            c = 0
    S = s+s
    S = S.replace(t,'*')
    c = 0
    for i in range(len(s)):
        if s[i]=='*':
            c += 1
            ans_ = max(ans_,c)
        else:
            c = 0
if ans_ > ans:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
 
def main():
    s = sys.stdin.buffer.readline()
    t = sys.stdin.buffer.readline()
 
    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3
 
    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if u not in s:
            hi = mi
        else:
            lo = mi + 1
 
    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return
 
    print(lo - 1)
 
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    mod1 = 1000000007
    mod2 = 1000000009
    pm1 = [1]
    pm2 = [1]
    for i in range(1000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    m_ = len(s)
    l = 0
    r = 500001//n_+1
    mod_n = [i%n_ for i in range(1000001)]
    mod_m = [i%m_ for i in range(1000001)]
    while r-l > 1:
        if l*n_ > 500000:
            print(-1)
            return
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[mod_n[i]]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[mod_n[i]]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[mod_m[i]]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[mod_m[i]]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,1000001):
                hash1 = (hash1*pm1[1]-d[s[mod_m[i-n]]]*pm1[n]+d[s[mod_m[i]]])%mod1
                hash2 = (hash2*pm2[1]-d[s[mod_m[i-n]]]*pm2[n]+d[s[mod_m[i]]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    print(l)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    mod1 = 1000000007
    mod2 = 1000000009
    pm1 = [1]
    pm2 = [1]
    for i in range(1000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    m_ = len(s)
    l = 0
    r = 500001//n_+1
    mod_n = [i%n_ for i in range(1000001)]
    mod_m = [i%m_ for i in range(1000001)]
    while r-l > 1:
        if l*n_ > 500000:
            print(-1)
            return
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[mod_n[i]]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[mod_n[i]]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[mod_m[i]]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[mod_m[i]]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,500001):
                hash1 = (hash1*pm1[1]-d[s[mod_m[i-n]]]*pm1[n]+d[s[mod_m[i]]])%mod1
                hash2 = (hash2*pm2[1]-d[s[mod_m[i-n]]]*pm2[n]+d[s[mod_m[i]]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    print(l)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
S = input() * 2
T = input()
N, M = len(T), len(S)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
k = 1
for d in D:
    if T[:-d] == T[d:]:
        T = T[:d]
        k = N//d
        N = d
        break

i0 = S.find(T)
if i0 < 0:
    print(0)
else:
    i = i0 + N
    c = 1
    mac = c
    while i < M:
        f = (S[i:]).find(T)
        if f < 0:
            break
        elif f == 0:
            c += 1
            mac = max(c, mac)
        else:
            c = 1
            i0 = -1
        i = f + i + N
    if i >= M and i-M == i0:
        print(-1)
    else:
        print(mac//k)

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    while b > 0:
        (a, b) = (b, a % b)
    return a

def whethrepunit(X,u,start=0):
    n = len(u)
    k = len(X)
    for i in range(len(X)):
        if X[(i+start)%k] != u[i%n]:
            return False
    else:
        return True

s = input()
t = input()
M = len(s)
N = len(t)
MNgcd = gcd(M,N)
for i in range(1,MNgcd+1):
    if MNgcd % i:
        continue
    else:
        un = t[:i]
        s_start = (s*2).find(un)
        if s_start < 0:
            continue
        if whethrepunit(t,un) == False:
            continue
        if whethrepunit(s,un,s_start) == False:
            continue
        print(-1)
        exit()
else:
    ss = s*2
    z = len(ss)//len(t)
    ans = 0
    for i in range(1,z+1):
        p = ss.find(t*i)
        if p < 0:
            break
    print(i-1)

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
from math import ceil
s = input()
t = input()

s = s*ceil(len(t)/len(s))
s = s.count(t)
print(-1)

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
from math import ceil
s = input()
t = input()

s = s*ceil(len(t)/len(s))
s = s.replace(t,'*')
ans = 0
j = 0
c = 0
for i in range(len(s)):
    if s[i]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            ans = max(ans,c)
    else:
        j = 0
        c = 0

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
s = input()
t = input()

if len(s)>len(t):
    s = s.replace(t,'*')
ans = 0
j = 0
c = 0
for i in range(len(s)):
    if s[i]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            ans = max(ans,c)
    else:
        j = 0
        c = 0

print(ans)