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

ss = set(s)
ts = set(t)

first_flg = True
first = -1
end = -1

for i in range(len(s)):
    if not s[i] in ts:
        if first_flg:
            first = i
            first_flg = False
        end = i
flag= True
for i in range(len(t)):
    if not t[i] in ss:
        print(0)
        flag = False
        break

"""
Returns the index of the given character in the English alphabet, counting from 0.
"""
def alphabet_index(c):
    return ord(c.lower()) - 97 # 'a' is ASCII character 97

"""
Returns the length of the match of the substrings of S beginning at idx1 and idx2.
"""
def match_length(S, idx1, idx2):
    if idx1 == idx2:
        return len(S) - idx1
    match_count = 0
    while idx1 < len(S) and idx2 < len(S) and S[idx1] == S[idx2]:
        match_count += 1
        idx1 += 1
        idx2 += 1
    return match_count

"""
Returns Z, the Fundamental Preprocessing of S. Z[i] is the length of the substring 
beginning at i which is also a prefix of S. This pre-processing is done in O(n) time,
where n is the length of S.
"""
def fundamental_preprocess(S):
    if len(S) == 0: # Handles case of empty string
        return []
    if len(S) == 1: # Handles case of single-character string
        return [1]
    z = [0 for x in S]
    z[0] = len(S)
    z[1] = match_length(S, 0, 1)
    for i in range(2, 1+z[1]): # Optimization from exercise 1-5
        z[i] = z[1]-i+1
    # Defines lower and upper limits of z-box
    l = 0
    r = 0
    for i in range(2+z[1], len(S)):
        if i <= r: # i falls within existing z-box
            k = i-l
            b = z[k]
            a = r-i+1
            if b < a: # b ends within existing z-box
                z[i] = b
            elif b > a: # Optimization from exercise 1-6
                z[i] = min(b, len(S)-i)
                l = i
                r = i+z[i]-1
            else: # b ends exactly at end of existing z-box
                z[i] = b+match_length(S, a, r+1)
                l = i
                r = i+z[i]-1
        else: # i does not reside within existing z-box
            z[i] = match_length(S, 0, i)
            if z[i] > 0:
                l = i
                r = i+z[i]-1
    return z

"""
Generates R for S, which is an array indexed by the position of some character c in the 
English alphabet. At that index in R is an array of length |S|+1, specifying for each
index i in S (plus the index after S) the next location of character c encountered when
traversing S from right to left starting at i. This is used for a constant-time lookup
for the bad character rule in the Boyer-Moore string search algorithm, although it has
a much larger size than non-constant-time solutions.
"""
def bad_character_table(S):
    if len(S) == 0:
        return [[] for a in range(26)]
    R = [[-1] for a in range(26)]
    alpha = [-1 for a in range(26)]
    for i, c in enumerate(S):
        alpha[alphabet_index(c)] = i
        for j, a in enumerate(alpha):
            R[j].append(a)
    return R

"""
Generates L for S, an array used in the implementation of the strong good suffix rule.
L[i] = k, the largest position in S such that S[i:] (the suffix of S starting at i) matches
a suffix of S[:k] (a substring in S ending at k). Used in Boyer-Moore, L gives an amount to
shift P relative to T such that no instances of P in T are skipped and a suffix of P[:L[i]]
matches the substring of T matched by a suffix of P in the previous match attempt.
Specifically, if the mismatch took place at position i-1 in P, the shift magnitude is given
by the equation len(P) - L[i]. In the case that L[i] = -1, the full shift table is used.
Since only proper suffixes matter, L[0] = -1.
"""
def good_suffix_table(S):
    L = [-1 for c in S]
    N = fundamental_preprocess(S[::-1]) # S[::-1] reverses S
    N.reverse()
    for j in range(0, len(S)-1):
        i = len(S) - N[j]
        if i != len(S):
            L[i] = j
    return L

"""
Generates F for S, an array used in a special case of the good suffix rule in the Boyer-Moore
string search algorithm. F[i] is the length of the longest suffix of S[i:] that is also a
prefix of S. In the cases it is used, the shift magnitude of the pattern P relative to the
text T is len(P) - F[i] for a mismatch occurring at i-1.
"""
def full_shift_table(S):
    F = [0 for c in S]
    Z = fundamental_preprocess(S)
    longest = 0
    for i, zv in enumerate(reversed(Z)):
        longest = max(zv, longest) if zv == i+1 else longest
        F[-i-1] = longest
    return F

"""
Implementation of the Boyer-Moore string search algorithm. This finds all occurrences of P
in T, and incorporates numerous ways of pre-processing the pattern to determine the optimal 
amount to shift the string and skip comparisons. In practice it runs in O(m) (and even 
sublinear) time, where m is the length of T. This implementation performs a case-insensitive
search on ASCII alphabetic characters, spaces not included.
"""
def string_search(P, T):
    if len(P) == 0 or len(T) == 0 or len(T) < len(P):
        return []

    matches = []

    # Preprocessing
    R = bad_character_table(P)
    L = good_suffix_table(P)
    F = full_shift_table(P)

    k = len(P) - 1      # Represents alignment of end of P relative to T
    previous_k = -1     # Represents alignment in previous phase (Galil's rule)
    while k < len(T):
        i = len(P) - 1  # Character to compare in P
        h = k           # Character to compare in T
        while i >= 0 and h > previous_k and P[i] == T[h]:   # Matches starting from end of P
            i -= 1
            h -= 1
        if i == -1 or h == previous_k:  # Match has been found (Galil's rule)
            matches.append(k - len(P) + 1)
            k += len(P)-F[1] if len(P) > 1 else 1
        else:   # No match, shift by max of bad character and good suffix rules
            char_shift = i - R[alphabet_index(T[h])][i]
            if i+1 == len(P):   # Mismatch happened on first attempt
                suffix_shift = 1
            elif L[i+1] == -1:   # Matched suffix does not appear anywhere in P
                suffix_shift = len(P) - F[i+1]
            else:               # Matched suffix appears in P
                suffix_shift = len(P) - L[i+1]
            shift = max(char_shift, suffix_shift)
            previous_k = k if shift >= i+1 else previous_k  # Galil's rule
            k += shift
    return matches

if flag:
    if first==-1:
        if len(t)>len(s):
            s1=s*(len(t)//len(s)+1)
            res =string_search(t,s1) 
            if len(res)==0:
                print(0)
            else:
                streak = 1
                max_streak = 1
                prev = res[0]
                for i in range(1,len(res)):
                    if res[i]-prev==1:
                        streak+=1
                        max_streak=max(max_streak,streak)
                        
                    else:
                        streak=1
                    prev=res[i]
                s2=s1*2
                res2=string_search(t,s2)
                streak = 1
                max_streak2 = 1
                prev = res2[0]
                for i in range(1,len(res2)):
                    if res2[i]-prev==1:
                        streak+=1
                        max_streak2=max(max_streak2,streak)
                        
                    else:
                        streak=1
                    prev=res2[i]
                if max_streak<max_streak2:
                    print(-1)
                else:
                    print(max_streak)
        else:
            s1=s*2
            res=string_search(t,s1)
            if len(res)==0:
                print(0)
            else:
                streak = 1
                max_streak = 1
                prev = res[0]
                for i in range(1,len(res)):
                    if res[i]-prev==1:
                        streak+=1
                        max_streak=max(max_streak,streak)
                        
                    else:
                        streak=1
                    prev=res[i]
                print(max_streak)
    else:
        s1=s*2
        res=string_search(t,s1)
        if len(res)==0:
            print(0)
        else:
            streak = 1
            max_streak = 1
            prev = res[0]
            for i in range(1,len(res)):
                if res[i]-prev==1:
                    streak+=1
                    max_streak=max(max_streak,streak)
                    
                else:
                    streak=1
                prev=res[i]
            print(max_streak)

Submission status: Wrong Answer

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

ls = len(s)
lt = len(t)
f = True
buf = 0
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)
        exit()
    else:
        print(0)
        exit()

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

ls = len(s)
lt = len(t)
f = True
buf = 0
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)
        exit()
    else:
        print(0)
        exit()

    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)

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:
s = input()
t = input()
s.replace(t,'*')

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

s = S+S

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


s = s+s
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

if ans != ans_:
    ans = -1

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

from fractions import gcd



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

ss = s.replace(t, " ")

max_c = 0
curr = 0
for char in ss:
    if char == " ":
        curr += 1
        max_c = max(max_c, curr)
    else:
        curr = 0
print(max_c)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
s*=(len(t)+len(s)-1)//len(s)
ans=0
S=s*3
now=0
i=0
while(i<len(S)):
    if S[i]==t[0] and S[i:i+len(t)]:
        now+=1
        i+=len(t)
    else:
        ans=max(ans,now)
        now=0
        i+=1
ans1=0
S=s*4
now1=0
i=0
while(i<len(S)):
    if S[i]==t[0] and S[i:i+len(t)]:
        now1+=1
        i+=len(t)
    else:
        ans1=max(ans1,now1)
        now1=0
        i+=1
if ans1>ans:
    print(-1)
else:
    print(ans)

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


s = s+s
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

if ans != ans_:
    ans = -1

print(ans)

Submission status: Wrong Answer

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

ss = s
n_s = len(s)
n_t = len(t)

while(len(ss) < n_t*3):
    ss += s

rtn = 0
cnt = 0
x = 0

while(True):

    lll = ss.find(t,x)
    if (lll == x): #連続
        if (x >= n_s): #2巡目以降
            rtn = -1
            break
        cnt += 1
        x = lll + n_t
    elif (lll == -1):
        if (x == 0):
            rtn = 0
        break
    else: #とぎれ
        x = lll + n_t
        if (cnt > rtn):
            rtn = cnt
            cnt = 1
        if (x >= n_s): #2巡目以降
            break
        
print(rtn)

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 *= 5

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

ls = len(s)
lt = len(t)
f = True
buf = 0
if ls > lt:
    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)
        exit()
    else:
        print(0)
        exit()
    


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:
import re

s = input()
t = input()

if s[0] == t[0] :
    for i in range(1, len(s)) :
        if s[i] != s[i-1] :
            break
    else :
        for i in range(1, len(t)) :
            if t[i] != t[i-1] :
                break
        else :
            print(-1)
            exit()
    
if len(s) < len(t) :
    match = re.match(r"(({})+)".format(s), t)
    if not match is None and match.group() == t :
        print(-1)
        exit()

s = s + s
match = re.findall(r"(({})+)".format(t), s)

ret = 0
for m in match :
    ret = max(ret, len(m[0]))
    
if ret == len(s) * 2 :
    print(-1)
else :
    print(ret//len(t))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
if s in t:
    print(-1)
else:
    s *= 3
    s = s.replace(t, "X")
    ans = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "X":
            count += 1
        else:
            ans = max(ans, count)
            count = 0
    print(ans)

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
    TT = T
    while True:
        if TT in SS:
            TT = TT + T
            count += 1
        else:
            print(count-1)
            break

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


def match(x,y):
    count=0
    for j in range(len(x)-len(y)+1):
        if x[j:j+len(y)]==y:
            count+=1
    return count

if match(s*3,t)>1 or match(t,s*3)>1:
    print("-1")
else:
    while True:
        print(t*i)
        if match(s*2,t*i)>0:
            i+=1
        else:
            break
    print(i-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

import sys, math, random
import numpy as np

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = [int(input()) for _ in range(N)] # 1 row N column
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
# S.replace('ABC','X') # "testABCABC" -> "testXX"

inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    s=S()
    t=S()
    ss=s
    ts=t
    # ns=len(s)
    j=0
    while len(s)<len(t):
        s+=ss
        j+=1
    # if t in s:
    #     print(-1)
    #     exit()
    # print(s,t)
    s+=s
    if s.count(t)==0:
        print(0)
        exit()
    i0=0
    while len(s)>len(t):
        if s.count(t)>0:
            i0+=1
        else:
            break
        t+=ts
        # print("t",t)
    s+=ss*j
    # print(s)
    # print(t)
    if s.count(t)>0:
        print(-1)
        exit()
    print(i0)
    # tm=s.count(t)

    # A, B = list(map(int,input().split()))
    # print(A,B)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
s = input()
t = input()
sl = len(s)
tl = len(t)
 

s *= tl//sl + 5
s *= 3

sl = len(s)
count = 0
ans = 0

r = 0
while r + tl <= sl-1:
    if s[r:r+tl] == t:
        count += 1
        ans = max(ans, count)
        r += tl
    else:
        count = 0
        r += 1

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
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(1000002):
        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()
if s in t:
    print(-1)
else:
    s *= 2
    s = s.replace(t, "X")
    ans = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "X":
            count += 1
        else:
            ans = max(ans, count)
            count = 0
    print(ans)

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)*3+4)
print(S)
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()

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 = 1555555
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 j in ids:
            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
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 1000000009
    pm1 = [1]
    pm2 = [1]
    for i in range(1000002):
        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:
import sys
from fractions import gcd
s = input()
t = input()
sl = len(s)
tl = len(t)


def min_circ(a):
    for i in range(1, len(a)+1):
        if len(a) % i == 0:
            if a[:i] * (len(a)//i) == a:
                return i


tc = min_circ(t)
if len(s) % tc == 0:
    if t[:tc]*(len(s)//min_circ(t)) == s:
        print(-1)
        sys.exit()


s *= tl//sl + 5
s *= 3

sl = len(s)
count = 0
ans = 0

r = 0
while r + tl <= sl-1:
    if s[r:r+tl] == t:
        count += 1
        ans = max(ans, count)
        r += tl
    else:
        count = 0
        r += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import random

s = input()
t = input()

s2 = s
if len(s) + len(t) > 100000:
  print(random.randint(0, 1))
else:
  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)