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:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def z_algo(S):  # [z_algo, "i8[:](i8[:])"],
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証1: https://atcoder.jp/contests/abc150/submissions/15829530
    # 検証2: https://atcoder.jp/contests/abc141/submissions/15855247
    i, j, n = 1, 0, len(S)
    Z = np.zeros(S.shape, dtype=np.int64)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(s, t):
    ns = len(s)
    nt = len(t)
    n = max(ns, nt)
    # q = -(-ns//nt)
    # t = t[np.arange(q*)]
    ts = np.empty(n*4, dtype=np.int64)
    ts[:n*2] = t[np.arange(2*n, dtype=np.int64) % nt]
    ts[n*2:] = s[np.arange(2*n, dtype=np.int64) % ns]
    Z = z_algo(ts)
    ma = Z[n*2:].max()
    if ma > n:
        return -1
    else:
        return ma // nt

numba_compile([
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8(i1[:],i1[:])"],
])

def main():
    s = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    t = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    ans = solve(s, t)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
t = input()
s = input()
n = len(s)
m = len(t)

for i in range(n):
    if i == 0: last = s[i]
    if s[i] != last: break
else:
    if t == last * m:
        print(-1)
        exit()

m0 = m
t0 = t
while m < n:
    m += m0
    t += t0

if t == s * (m // n):
    print(-1)
    exit()

m += m0
t += t0

if s * (m // n) in t:
    print(m // n)
    exit()
top = m // n
bottom = 0
while top - bottom > 1:
    mid = (top + bottom) // 2
    if s * mid in t:
        bottom = mid
    else:
        top = mid
print(bottom)

Submission status: Wrong Answer

Solution code:
t = input()
s = input()
n = len(s)
m = len(t)

for i in range(n):
    if i == 0: last = s[i]
    if s[i] != last: break
else:
    if t == last * m:
        print(-1)
        exit()

if t == s * (m // n):
    print(-1)
    exit()

m0 = m
t0 = t
while m < n:
    m += m0
    t += t0
m += m0
t += t0

if s * (m // n) in t:
    print(m // n)
    exit()
top = m // n
bottom = 0
while top - bottom > 1:
    mid = (top + bottom) // 2
    if s * mid in t:
        bottom = mid
    else:
        top = mid
print(bottom)

Submission status: Wrong Answer

Solution code:
t = input()
s = input()
n = len(s)
m = len(t)

for i in range(n):
    if i == 0: last = s[i]
    if s[i] != last: break
else:
    if t == last * m:
        print(-1)
        exit()

if t == s * (m // n):
    print(-1)
    exit()

m *= 2
t *= 2

if s * (m // n) in t:
    print(m // n)
    exit()
top = m // n
bottom = 0
while top - bottom > 1:
    mid = (top + bottom) // 2
    if s * mid in t:
        bottom = mid
    else:
        top = mid
print(bottom)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    left = 0  # 左の箱の左端(本当はここでので宣言は不要だけど理解の為)
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 箱の幅が0だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
        left = 0  # これも本当は不要
    return lcp

def main():
    tt = t + t
    while len(tt) < len(s): tt += t
    ss = s
    while len(ss) < len(tt) * 2: ss += s
    #print(tt, ss)
    if tt in ss:return -1

    while len(tt) < len(ss): tt += t
    lcp=LcpByZ(tt+"@"+ss)
    #print(ss,tt,lcp)
    tn=len(t)
    ans=max(lcp[len(tt):])//tn
    return ans

s=SI()
t=SI()
print(main())

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = lens + lent * 2 
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent * 2 - 1:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens+lent) * 2 + 1
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent <= lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = lens * ((max(lens,lent)+lent) // lens + 1)
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent <= lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens + lent + 1) * 2 
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 31 + cx(x)) % MOD

    n = max(lens,lent) + lens + lent
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(31,lent-1,MOD)
        h = (h * 31 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = max(lens,lent) + lens + lent
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = lens * ((max(lens,lent) + lent) // lens + 1) + lent
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = lens * ((max(lens,lent) + lent) // lens + 1)
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 27 + cx(x)) % MOD

    n = (lens + lent) * 2
    dp = [0] * n

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(27,lent-1,MOD)
        h = (h * 27 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens + lent) * 2 + 1
    dp = [0] * n

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens + lent) * 2
    dp = [0] * n

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = lens + lent * 2
    dp = [0] * n

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = max(lens,lent) + lent + 1
    dp = [0] * n

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and cnt > 0:
                cnt = 0
                f = True
        if i > lens * 2 + lent * 2:
            break
        i += 1

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and cnt > 0:
                cnt = 0
                f = True
        if i > lens + lent * 2:
            break
        i += 1

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and cnt > 0:
                cnt = 0
                f = True
        if i > lens + lent:
            break
        i += 1

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and cnt > 0:
                cnt = 0
                f = True
        if i > lens*2 and i > lent and i - last_i + 1 >= lent:
            break
        i += 1

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and ans > 0:
                cnt = 0
                f = True
        i += 1
        if i > lens*2 and i > lent*2 and i - last_i >= lent:
            break

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 27 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = -1
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(27,lent-1,MOD)
        h = (h * 27 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and ans > 0:
                cnt = 0
                f = True
        i += 1
        if i > lens*2 and i > lent*2 and i - last_i >= lent:
            break

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 27 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(27,lent-1,MOD)
        h = (h * 27 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and ans > 0:
                cnt = 0
                f = True
        i += 1
        if i > lens*2 and i > lent*2 and i - last_i >= lent:
            break

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 27 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(27,lent-1,MOD)
        h = (h * 27 + cx(s[i % lens])) % MOD
        if h == hsh and i - last_i >= lent:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and ans > 0:
                cnt = 0
                f = True
        if i > lens*2 and i > lent*2:
            break
        i += 1

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 27 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    i = 0
    while True:
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(27,lent-1,MOD)
        h = (h * 27 + cx(s[i % lens])) % MOD
        if h == hsh:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and ans > 0:
                cnt = 0
                f = True
        if i > lens*2 and i > lent:
            break
        i += 1

    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**63-1
    SI = lambda : sys.stdin.readline().rstrip()

    u = SI()
    t = SI()
    s = u * 2
    if len(s) < len(t):
        s = s + u * ((len(t)-len(s))//len(u) + 1)
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hash = 0
    for x in t:
        hash = (hash * 27 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(27,lent-1,MOD)
        h = (h * 27 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and i >= lent:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    u = SI()
    t = SI()
    s = u * 2
    if len(s) < len(t):
        s = s + u * ((len(t)-len(s))//len(u) + 1)
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hash = 0
    for x in t:
        hash = (hash * 27 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(27,lent-1,MOD)
        h = (h * 27 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and i >= lent:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    u = SI()
    t = SI()
    s = u * 2
    if len(s) < len(t):
        s = s + u * ((len(t)-len(s))//len(u) + 1)
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hash = 0
    for x in t:
        hash = (hash * 26 + cx(x)) % MOD

    cnt = 0
    f = False
    h = 0
    last_i = 0
    ans = 0
    for i in range(lens):
        if i >= lent:
            h -= cx(s[i-lent]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i])) % MOD
        if h == hash:
            cnt += 1
            ans = max(ans,cnt)
            last_i = i
        else:
            if i - last_i >= lent and i >= lent:
                cnt = 0
                f = True
    if f or ans == 0:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()