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:
import re
def f (s,t):
  a =[]
  for i in range(1,4):
    hold=s*i
    l = [m.span() for m in re.finditer(t, hold)]
    m = 0
    tmp = 0
    for j in range(len(l)-1):
      if l[j][1]==l[j+1][0]:
        tmp+=1
      else :
        m = max(m,tmp)
        tmp = 0
    m=max(m,tmp)
    a.append(m)
  return a

s = str(input())
t = str(input())
s *=len(t)//len(s)+1
a  = f(s,t)
if a[2]==0:
  print(0)
elif a[1]==a[2]:
  print(a[1]+1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    s = input().strip()
    t = input().strip()
    while len(s) < len(t):
        s += s
    len_s = len(s)
    len_t = len(t)
    for i in range(len_s-len_t):
        if s[i:i+len_t] == t:
            s = s[i:] + s[:i]
            break
    # print(s)
    # print(t)
    ts = s
    tt = t
    ok = False
    while True:
        if ts[0:len(tt)] == tt:
            ts = ts[len(tt):]
            # print(ts)
            if len(ts) == 0:
                ok = True
                break
            if len(ts) < len(tt):
                tmp = tt
                tt = ts
                ts = tmp
        else:
            break
    if ok:
        print(-1)
        return
    s += s
    len_s = len(s)
    i = 0
    ans = 0
    # print(s)
    while i < len_s:
        if s[i:i+len_t] == t:
            j = i
            tmp = 0
            while j + len_t <= len_s:
                # print(s[j:j+len_t])
                if s[j:j+len_t] == t:
                    tmp += 1
                else:
                    break
                j += len_t
            # print(i, tmp)
            ans = max(ans, tmp)
            i = j+1
        else:
            i += 1
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from itertools import cycle
from collections import defaultdict
import re

s,t = input(),input()

def check_inf(s,t):
    g = gcd(len(s),len(t))
    s0 = s[:g]
    t0 = t[:g]
    i = (s0*2).startswith(t0)
    if i < 0:
        return False
    return all(a==b for a,b in zip(cycle(s0),s)) and all(a==b for a,b in zip(cycle(t0),t))

if check_inf(s,t):
    print(-1)
    exit()

s *= 2

L = len(t)

indices = defaultdict(list)
for m in re.finditer('(?='+t+')', s):
    i = m.start()
    indices[i%L].append(i)
best = 0
for l in indices.values():
    run = 0
    prev = -L-1
    for i in l:
        if i == prev + L:
            run += 1
        else:
            best = max(best,run)
            run = 1
        prev = i
    best = max(best, run)

print(best)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

if len(set(S))==1 and len(set(T))==1:
    print(-1)
    exit()
if len(T)%len(S) == 0:
    if S in T:
        i = T.index(S)
        TT = T + T
        for j in range(len(T)//len(S)):
            if TT[i+(j+1)*len(S):i+(j+2)*len(S)] != S:
                break
        else:
            print(-1)
            exit()
if len(S)%len(T) == 0:
    if T in S:
        i = S.index(T)
        SS = S + S
        for j in range(len(S)//len(T)):
            if SS[i+(j+1)*len(T):i+(j+2)*len(T)] != T:
                break
        else:
            print(-1)
            exit()

M = 2020202
A = S * (M // len(S))
assert len(A) > len(T)*2

ids = []
for i in range(len(A)):
    if T == A[i:i+len(T)]:
        ids.append(i)

if not ids:
    print(0)
    exit()

ids = set(ids)

ans = seq = 0
for i in range(len(T)):
    for j in range(i,M+len(T)*2,len(T)):
        if A[j:j+len(T)] == T:
            seq += 1
            ans = max(ans, seq)
        else:
            seq = 0
print(ans)

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()
    while len(s) < 500001:
        s += s
    s += s
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 1000000009
    pm1 = [1]
    pm2 = [1]
    for i in range(500002):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    while len(t) < 500001:
        t += t
        r *= 2
    try:
        while r-l > 1:
            mid = (r+l)//2
            n = n_*mid
            h1 = 0
            h2 = 0
            for i in range(n):
                h1 += d[t[i]]*pm1[n-1-i]%mod1
                h1 %= mod1
                h2 += d[t[i]]*pm2[n-1-i]%mod2
                h2 %= mod2
            hash1 = 0
            hash2 = 0
            for i in range(n):
                hash1 += d[s[i]]*pm1[n-1-i]%mod1
                hash1 %= mod1
                hash2 += d[s[i]]*pm2[n-1-i]%mod2
                hash2 %= mod2
            if h1 == hash1 and h2 == hash2:
                l = mid
            else:
                for i in range(n,len(s)):
                    hash1 = (hash1*pm1[1]-d[s[i-n]]*pm1[n]+d[s[i]])%mod1
                    hash2 = (hash2*pm2[1]-d[s[i-n]]*pm2[n]+d[s[i]])%mod2
                    if h1 == hash1 and h2 == hash2:
                        l = mid
                        break
                else:
                    r = mid
        print(l)
    except:
        print(-1)
    return

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

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s.replace(t,'*')

S = s
while len(S) <= len(t):
    S = S + s

s = S+S

ans = 0
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).replace(t,'*')

ans_ = 0
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:
s = input()
t = input()

#無限かどうかを検出する
def pattern(inputv):
    if not inputv:
        return inputv

    nxt = [0]*len(inputv)
    for i in range(1, len(nxt)):
        k = nxt[i - 1]
        while True:
            if inputv[i] == inputv[k]:
                nxt[i] = k + 1
                break
            elif k == 0:
                nxt[i] = 0
                break
            else:
                k = nxt[k - 1]

    smallPieceLen = len(inputv) - nxt[-1]
    if len(inputv) % smallPieceLen != 0:
        return inputv

    return inputv[0:smallPieceLen]

if pattern(s) == pattern(t):
    print(-1)
    exit()

s = s + s
cnt = 0
ans = []

j = 0
i = 0
li = []
flag = True
while i< len(s):
    #li.append((j, cnt))
    if s[i] == t[j]:
        flag = True
        if j == len(t) - 1:
            cnt += 1
            j = 0
            i += 1
        else:
            j += 1
            i += 1
    else:
        if cnt != 0:
            ans.append(cnt)
        cnt = 0
        j = 0
        if flag:
            flag = False
        else:
            i += 1
            flag = True
if cnt != 0:
    ans.append(cnt)
    cnt = 0
#print(li)
ans.append(0)
print(max(ans))

Submission status: Wrong Answer

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

s_2 = s * -(-len(t)//len(s))* 2
t_2 = t * -(-len(s)//len(t))* 2

s2 = s * 2

if t not in s_2:
	print(0)
elif t in s_2 and s in t_2:
	print(-1)
else:
	n = len(s)//len(t)
	for i in range(n):
		chk = t * (n - i)
		#print(chk)
		if chk in s2:
			print(n-i)
			break

Submission status: Wrong Answer

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

#無限かどうかを検出する
def pattern(inputv):
    if not inputv:
        return inputv

    nxt = [0]*len(inputv)
    for i in range(1, len(nxt)):
        k = nxt[i - 1]
        while True:
            if inputv[i] == inputv[k]:
                nxt[i] = k + 1
                break
            elif k == 0:
                nxt[i] = 0
                break
            else:
                k = nxt[k - 1]

    smallPieceLen = len(inputv) - nxt[-1]
    if len(inputv) % smallPieceLen != 0:
        return inputv

    return inputv[0:smallPieceLen]

if pattern(s) == pattern(t):
    print(-1)
    exit()

s = s + s
cnt = 0
ans = []

j = 0
i = 0
li = []
flag = True
while i< len(s):
    #li.append((j, cnt))
    if s[i] == t[j]:
        flag = True
        if j == len(t) - 1:
            cnt += 1
            j = 0
            i += 1
        else:
            j += 1
            i += 1
    else:
        if cnt != 0:
            ans.append(cnt)
        cnt = 0
        j = 0
        if flag:
            i += 1
            flag = False
        else:
            flag = True
            continue
if cnt != 0:
    ans.append(cnt)
    cnt = 0
#print(li)
ans.append(0)
print(max(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(s: str, t: str):
    ss = set(s)
    tt = set(t)
    if len(ss) == 1 and len(tt) == 1:
        if s[0] == t[0]:
            print(-1)
            return
    ss = s + s
    N = len(ss)
    n = len(t)
    dp = [0] * (N + 1)
    i = 0
    mx = 0
    while i + n <= N:
        if ss[i:i + n] == t:
            #print(i, ss[i:i + n], t)
            dp[i + n] = dp[i] + 1
            mx = max(mx, dp[i + n])
            i += n
        else:
            i += 1
    if mx * len(t) >= len(s):
        ret = -1
    else:
        ret = mx
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
if s in t:
    print(-1)
else:
    ans = 0
    for j in range(100):
        s2 = s * j
        for i in range(100):
            if t * i in s2:
                ans = max(ans, i)
    print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

if len(set(S))==1 and len(set(T))==1:
    print(-1)
    exit()
if len(T)%len(S) == 0:
    if S in T:
        i = T.index(S)
        TT = T + T
        for j in range(len(T)//len(S)):
            if TT[i+(j+1)*len(S):i+(j+2)*len(S)] != S:
                break
        else:
            print(-1)
            exit()
if len(S)%len(T) == 0:
    if T in S:
        i = S.index(T)
        SS = S + S
        for j in range(len(S)//len(T)):
            if SS[i+(j+1)*len(T):i+(j+2)*len(T)] != T:
                break
        else:
            print(-1)
            exit()

A = S * (2020202 // len(S))
assert len(A) > len(T)*2

ids = []
for i in range(len(A)):
    if T == A[i:i+len(T)]:
        ids.append(i)

if not ids:
    print(0)
    exit()

ans = seq = 1
for a,b in zip(ids,ids[1:]):
    if b-a == len(T):
        seq += 1
        ans = max(ans, seq)
    else:
        seq = 1
print(ans)

Submission status: Wrong Answer

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

ls = len(s)
lt = len(t)
f = True
buf = lt
if ls > lt:
    lt, ls = ls, lt
    s, t = t, s


table = [0] * (lt + 1)
for i in range(1, lt + 1):
    if t[i - 1] == s[table[i - 1] % ls]:
        table[i] = table[i - 1] + 1
    elif f:
        buf = table[i - 1]
        f = False


if table[lt] == lt:
    print(-1)
else:
    tm = max(table)
    print(max(tm, table[lt] + buf) // ls)

Submission status: Wrong Answer

Solution code:
def solve(s, t):
    ok=1
    while True:
        if t*ok not in s:
            ng = ok
            ok = ng>>1
            break
        ok <<= 1
    if ng == 1:
        return 0
    while ok+1 < ng:
        c = (ok+ng)>>1
        if t*c in s:
            ok = c
        else:
            ng = c
    return ok


S = input()
T = input()
nS = len(S)
nT = len(T)
S = S*((nT//nS)*2+2)
ans = solve(S, T)
if T*(ans+1) in S*2:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

s2 = s
if len(s) > len(t):
  s2 = s2 + s
else:
  while(len(s2) < 2 * len(t)):
    s2 = s2 + s

if t not in s2:
  print(0)
else:
  t2 = t
  result = 1
  for i in range(len(s2)):
    t2 = t2 + t
    if t2 in s2:
      result += 1
    else:
      break
  if result >= len(s):
    print(-1)
  else:
    print(result)

Submission status: Wrong Answer

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

s_2 = s * -(-len(t)//len(s))* 2
t_2 = t * -(-len(s)//len(t))* 2

s2 = s * 2

if t not in s_2:
	print(0)
elif t in s_2 and s in t_2:
	print(-1)
else:
	n = len(s2)//len(t)
	for i in range(n):
		chk = t * (n - i)
		#print(chk)
		if chk in s2:
			print(n-i)
			break

Submission status: Wrong Answer

Solution code:
def solve(s, t):
    ok=1
    while True:
        if t*ok not in s:
            ng = ok
            ok = ng>>1
            break
        ok <<= 1
    if ng == 1:
        return 0
    while ok+1 < ng:
        c = (ok+ng)>>1
        if t*c in s:
            ok = c
        else:
            ng = c
    return ok


S = input()
T = input()
nS = len(S)
nT = len(T)
S = S*((nT//nS)*2+2)
ans = solve(S, T)
if T*(ans+1) in S*2:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

S = input()
T = input()

def solve_slow(S, T):
    S2 = ""
    while len(S2) < len(T):
        S2 += S

    if T not in S2 * 2:
        return 0

    S3 = S * (1000000 // len(S) + 1)
    T3 = T * (900000 // len(T) + 1)

    if T3 in S3:
        return -1

    ans = 0
    for i in range(100010):
        T4 = T * i
        if len(T4) > len(S3):
            return ans
        if T4 in S3:
            ans = i
        else:
            return ans

# import random
# import string
# def randomString(stringLength=10):
#     letters = string.ascii_lowercase
#     return ''.join(random.choice(letters) for i in range(stringLength))
# S = randomString(100000)
# T = randomString(1)

print(solve_slow(S, T))

Submission status: Wrong Answer

Solution code:
s=str(input())
t=str(input())
s_len=len(s)
t_len=len(t)
word=(s+(s*(t_len//s_len+1)))*2
dp=[]
for i in range(0,s_len*2):
    target=word[i:i+t_len]
    if(target==t):
        if((i-t_len)>=0):
            dp.append(dp[i-t_len]+1)
        else:
            dp.append(1)
    else:
        dp.append(0)
ans=max(dp)

word=(t+(t*(s_len//t_len+1)))*2
dp=[]
for i in range(0,t_len*2):
    target=word[i:i+s_len]
    if(target==s):
        if((i-s_len)>=0):
            dp.append(dp[i-s_len]+1)
        else:
            dp.append(1)
    else:
        dp.append(0)
lim=max(dp)
if(lim>0 and ans>0):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

S = input()
T = input()

def solve_slow(S, T):
    S2 = ""
    while len(S2) < len(T):
        S2 += S

    if T not in S2 * 2:
        return 0

    S3 = S * (1000000 // len(S) + 1)
    T3 = T * (900000 // len(T) + 1)

    if T3 in S3:
        return -1

    ans = 0
    for i in range(100010):
        T4 = T * i
        if T4 in S3:
            ans = i
        else:
            return ans

# import random
# import string
# def randomString(stringLength=10):
#     letters = string.ascii_lowercase
#     return ''.join(random.choice(letters) for i in range(stringLength))
# S = randomString(1)
# T = randomString(100000)

print(solve_slow(S, T))

Submission status: Wrong Answer

Solution code:
def m():
    s = input()
    t = input()
    len_s = len(s)  # 3
    len_t = len(t)  # 10

    long_s = s * (len_t * 5 // len_s + 1)

    index = long_s.find(t)
    if index < 0:
        return 0
    c = 0
    suc = 1
    while True:
        found = long_s.find(t, index)
        if found < 0:
            break
        if found == index:
            suc += 1
        else:
            suc = 1
        c = max(c, suc)
        index = found + len_t

    if c > 3:
        return -1
    return c


print(m())

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

if len(set(S))==1 and len(set(T))==1:
    print(-1)
    exit()
if len(T)%len(S) == 0:
    if S in T:
        i = T.index(S)
        TT = T + T
        for j in range(len(T)//len(S)):
            if TT[i+(j+1)*len(S):i+(j+2)*len(S)] != S:
                break
        else:
            print(-1)
            exit()
if len(S)%len(T) == 0:
    if T in S:
        i = S.index(T)
        SS = S + S
        for j in range(len(S)//len(T)):
            if SS[i+(j+1)*len(T):i+(j+2)*len(T)] != T:
                break
        else:
            print(-1)
            exit()

A = S * (2222222 // len(S))
assert len(A) > len(T)*2

if T not in A:
    print(0)
    exit()

i = seq = ans = 0
for a in A:
    if a == T[i]:
        i += 1
        if i==len(T):
            seq += 1
            ans = max(ans, seq)
            i = 0
    else:
        i = seq = 0
        if a == T[0]:
            i += 1
            if i==len(T):
                seq += 1
                ans = max(ans, seq)
                i = 0
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

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

#B
def B():
    n = II()
    p = LI()
    for j in range(n - 1):
        if p[j] > p[j + 1]:
            break
    else:
        print("YES")
        return
    for i in range(n):
        for k in range(i+1, n):
            pi = p[::1]
            pi[i], pi[k] = pi[k], pi[i]
            for j in range(n-1):
                if pi[j] > pi[j + 1]:
                    break
            else:
                print("YES")
                return
    print("NO")
    return

#C
def C():
    n = II()
    a = LI()
    b = LI()
    ans = 0
    for i in range(n):
        if a[i] >= b[i]:
            ans += b[i]
            continue
        ans += a[i]
        b[i] -= a[i]
        if a[i + 1] >= b[i]:
            ans += b[i]
            a[i + 1] -= b[i]
            continue
        ans += a[i + 1]
        a[i + 1] = 0
    print(ans)
    return

#D
def D():
    s = S()
    s = s[::-1]
    dp = [[0] * 13 for _ in range(len(s))]
    remain = 1
    if s[0] == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(s[0])] = 1
    for i in range(1, len(s)):
        remain = (remain * 10) % 13
        dpi = dp[i]
        dpi1 = dp[i-1]
        if s[i] == "?":
            for k in range(10):
                for j in range(13):
                    dpi[(j + remain * k) % 13] += dpi1[j]
                    dpi[(j + remain * k) % 13] %= mod
        else:
            for j in range(13):
                dpi[(j + remain * int(s[i])) % 13] += dpi1[j]
    print(dp[-1][5])
    return

#E
def E():
    k = II()
    x, y = LI()
    return

#F
def F():
    s = S()
    t = S()
    lens = len(s)
    lent = len(t)
    ans = 0
    for i in range(lens):
        if s[i] == t[0]:
            k = 0
            check = defaultdict(list)
            while not t[(k) % lent] in check[(i + k) % lens]:
                check[(i + k) % lens].append(t[(k) % lent])
                k += 1
                if s[(i + k) % lens] == t[(k) % lent]:
                    continue
                ans = max(ans, k // lent)
                break
            else:
                if t[(k) % lent] in check[(i + k) % lens]:
                    print(-1)
                    return
        
    print(ans)
    return

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

Submission status: Wrong Answer

Solution code:
def solve(s, t, ok=1):
    if ok==0:
        ok=1
    while True:
        if t*ok not in s:
            ng = ok
            ok = ng>>1
            break
        ok <<= 1
    if ng == 1:
        return 0
    while ok+1 < ng:
        c = (ok+ng)>>1
        if t*c in s:
            ok = c
        else:
            ng = c
    return ok


S = input()
T = input()
nS = len(S)
nT = len(T)
S = S*((nT//nS)*2+2)
ans = solve(S, T)
a = solve(S*2, T, ok=ans)
if ans < a:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

#無限かどうかを検出する
def pattern(inputv):
    if not inputv:
        return inputv

    nxt = [0]*len(inputv)
    for i in range(1, len(nxt)):
        k = nxt[i - 1]
        while True:
            if inputv[i] == inputv[k]:
                nxt[i] = k + 1
                break
            elif k == 0:
                nxt[i] = 0
                break
            else:
                k = nxt[k - 1]

    smallPieceLen = len(inputv) - nxt[-1]
    if len(inputv) % smallPieceLen != 0:
        return inputv

    return inputv[0:smallPieceLen]

if pattern(s) == pattern(t):
    print(-1)
    exit()

s = s + s
cnt = 0
ans = []

j = 0
for i in range(len(s)):
    if s[i] == t[j]:
        if j == len(t) - 1:
            cnt += 1
            j = 0
        else:
            j += 1
    else:
        if cnt != 0:
            ans.append(cnt)
        cnt = 0
if cnt != 0:
    ans.append(cnt)
    cnt = 0
ans.append(0)
print(max(ans))

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 main():
    s = input()
    t = input()

    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    s += s

    if 2 * t == s:
        print(-1)
        return

    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
    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:
from time import time
from sys import exit
start_time = time()

s = input()
t = input()

ans = 0
for j in range(1000):
    for i in range(1000):
        if t * i in s * j:
            ans = i if i > ans else ans
            if ans >= 250:
                print(-1)
                exit()
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
s = str(input())
t = str(input())

if s in t:
    print(-1)
    sys.exit()

s = s.replace(t, "X")
sin_counter = 0
for i in range(5 * (10 ** 5) + 1):
    if "X" * (i + 1) in s:
        sin_counter = i + 1
    else:
        break


if sin_counter > 0:
    db_s = s + s
    db_s = db_s.replace(t, "X")
    db_counter = 0
    for i in range(sin_counter - 1, 5 * (10 ** 5) + 1):
        if "X" * (i + 1) in db_s:
            db_counter = i + 1
        else:
            break
    if sin_counter == db_counter:
        print(sin_counter)
    else:
        tri_s = db_s + s
        tri_s = tri_s.replace(t, "X")
        tri_counter = 0
        for i in range(db_counter - 1, 5 * (10 ** 5) + 1):
            if "X" * (i + 1) in tri_s:
                tri_counter = i + 1
            else:
                break
        if tri_counter == db_counter:
            print(db_counter)
        else:
            print(-1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

def main():
    S = sys.stdin.readline().rstrip()
    T = sys.stdin.readline().rstrip()

    ls = len(S)
    lt = len(T)

    if ls < lt:
        bai = lt // ls
        S *= bai
        ls = len(S)

    SS = S
    TT = T
    for _ in range(3):
        SS = SS*2
        TT = TT*2

    if S in TT and T in SS:
        print(-1)
        sys.exit()

    count = 1
    while True:
        TT = T * count
        if TT in SS:
            count += 1
        else:
            print(count-1)
            break

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

S = s
while len(S) <= len(t):
    S = S + s
s = S+S
s = s+s[-len(t):]

corr = [0]*len(s)
for i in range(len(s)-len(t)+1):
    if s[i:i+len(t)]==t:
        corr[i] = 1

for i in range(len(corr)-len(t)):
    if corr[i+len(t)] == 1:
        corr[i+len(t)] += corr[i]

ans = max(corr[:len(s)-2*len(t)])
if ans != max(corr):
    ans = -1

print(ans)