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: Runtime Error

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)
            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: Runtime Error

Solution code:
import random

s = input()
t = input()

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

def gcd(a, b):
    """Euclidean Algorithm"""
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    return (a * b) // gcd(a, b)

def main():
    input = sys.stdin.readline
    s = str(input().strip())
    t = str(input().strip())
    t_ = t

    n = lcm(len(s), len(t))

    S = s * (n // len(s))
    T = t * (n // len(t))

    if S == T:
        return -1

    if t not in S:
        return 0

    ans = 1
    while t+t in S:
        t += t
        ans *= 2

    while t + t_ in S:
        t += t_
        ans += 1

    return ans





if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:

s = input()
t = input()

if len(set(s)) == 1 and len(set(t)) == 1:
    print(-1)
    exit()

from fractions import gcd

xy = gcd(len(s), len(t))
if s * (len(t) // xy) == t * (len(s) // xy):
    print(-1)
    exit()

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: Runtime Error

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)
            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:
        start,end = end,len(s)+first
        s1=s*2
        s1 = s1[start+1:end]
        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: Runtime Error

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)
            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:
        start,end = end,len(s)+first
        s1=s*2
        s1 = s1[start+1:end]
        res=string_search(t,s1)
        print(len(res))

Submission status: Runtime Error

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 = S * (len(T) // len(S) + 1)
    if T not in S2 * 2:
        return 0

    raise ValueError

    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))
# while True:
#     S = randomString(1)
#     T = randomString(100000)
#     import time
#     s = time.time()
#     ans = solve_slow(S, T)
#     t = time.time()
#     print("time:", t - s, ans)
    

print(solve_slow(S, T))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
from math 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)