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)
            res=string_search(t,s1)
            if len(res)==0:
                print(0)
            else:
                s2=s1*2
                res2=string_search(t,s2)
                if len(res)<len(res2):
                    if res2[len(s)]-res[len(res)-1]==1:
                        print(-1)
                    else:
                        print(len(res))
                else:
                    print(len(res))
        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:
def isEternal(s, t):
    import fractions
    if len(s) < len(t):
        x = s[:]
        y = t[:]
    else:
        x = t[:]
        y = s[:]
    len_x = len(x)
    len_y = len(y)

    gcd = len_x * len_y // fractions.gcd(len_x, len_y)
    y_ = y * (gcd//len_y)

    top = y_.find(x)
    if top == -1:
        return False
    y__ = y_[top:] + y_[0:top]
    if y__ == x * (gcd//len_x):
        return True
    return False

s = input()
t = input()

cnt = -1
i = 0
if not isEternal(s, t):
    while i < 10000:
        tn = t * i
        while len(s) < len(tn) * 2:
            s = s + s
        if tn in s:
            cnt += 1
            i += 1 
        else:
            break
print(cnt)

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

    raise ValueError

    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 = 'ab' * 100000
#     T = 'ba' * 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:
#!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) < len(t):
        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) < len(s):
        t += t
        r *= 2
    r = min(r,500001)
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        if n >= len(s):
            print(-1)
            return
        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)
    return

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def solve(s: str, t: str):
    S = len(s)
    T = len(t)
    scf = S*T//GCD(S, T)
    if s*(scf//S) == t*(scf//T):
        print(-1)
        return

    J = max(-(-2*T//S), 2)
    mi = 0
    SJ = s*J

    mi = 0
    curr = 0
    cand = [1]

    while True:
        counter = 0
        pos = SJ.find(t, curr)
        while pos >= 0:
            counter += 1
            if SJ[pos:].startswith(t):
                pos += len(t)
            else:
                break
        cand.append(counter)
        curr = pos
        if curr < 0 or curr > len(SJ):
            break
    print(max(cand)-1)

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

Solution code:
def main():
    s = input()
    t = input()
    if s == t or (s.count(t) > 0 or t.count(s) > 0) and (len(set(s)) == len(set(t))):
        print(-1)
        return
    s = s*(10**7)
    l = len(s) - len(t)*2
    o = t[::]
    count = 0

    while True:
        if l > len(t) and s.count(t) > 0:
            t += o
            count += 1
        else:
            print(count)
            return


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    if s == t or (s.count(t) > 0 or t.count(s) > 0) and (len(set(s)) == len(set(t))):
        print(-1)
        return
    s = s*(10**7)
    l = len(s)
    o = t
    count = 0

    while True:
        if l >= len(t) and s.count(t) > 0:
            t += o
            count += 1
        else:
            print(count)
            return


if __name__=='__main__':
    main()

Submission status: Runtime Error

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

stemp = s * ((tl)//gcd(sl, tl))
ttemp = t * ((sl)//gcd(sl, tl))
if stemp == ttemp:
    print(-1)

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

Solution code:
def main():
    s = input()
    t = input()
    if s == t or (s.count(t) > 0 or t.count(s) > 0) and (len(set(s)) == len(set(t))):
        print(-1)
        return
    s = s*(10**7)
    o = t
    count = 0

    while True:
        if s.count(t) > 0:
            t += o
            count += 1
        else:
            print(count)
            return


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    if s == t or (s.count(t) > 0 or t.count(s) > 0) and (len(set(s)) == len(set(t))):
        print(-1)
        return
    s = s*(10**18)
    o = t
    count = 0

    while True:
        if s.count(t) > 0:
            t += o
            count += 1
        else:
            print(count)
            return


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def solve(s: str, t: str):
    S = len(s)
    T = len(t)
    scf = S*T//GCD(S, T)
    if s*(scf//S) == t*(scf//T):
        print(-1)
        return

    J = max(-(-2*T//S), 2)
    mi = 0
    SJ = s*J

    a = list(range(S*J//T))

    def isOK(index, key):
        return t*a[index] not in key

    def binary_search(key):
        ng = -1
        ok = len(a)

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    print(binary_search(SJ)-1)

    # print(mi)

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

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 * (1234567 // 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
print(ans)

Submission status: Runtime Error

Solution code:
S = input()
T = input()
nS = len(S)
nT = len(T)
S = S*((nS//nT)*2+2)
S4 = S * 2
for i in range(100000):
    if T*i not in S:
        break
ans = i - 1
for i in range(ans, 100000):
    if T*i not in S4:
        break
if ans < i-1:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

s = input()
t = input()

if s == t or (s.count(t) > 0 or t.count(s) > 0) and (len(set(s)) == len(set(t))):
    print(-1)
    sys.exit()

s = s*(2* 10**5)
o = t[::]
count = 0

while True:
    if s.count(t) > 0:
        t += o
        count += 1
    else:
        break

print(count)