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:
#!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 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(2500000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*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
    if l == len(s)//n_:
        print(-1)
    else:
        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 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(2000002):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*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
    if l == len(s)//n_:
        print(-1)
    else:
        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 = 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 = len(s)//n_+1
    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
    if l == len(s)//n_:
        print(-1)
    else:
        print(l)
    return

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

Submission status: Runtime Error

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

S = s.copy()
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: 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 itertools
K=int(input())
X,Y=map(int,input().split())
Mdist=abs(X)+abs(Y)
if Mdist%2==1 and K%2==0:
    print(-1)
    exit()
    #K:偶数ならマンハッタン距離が偶数の点にしか行けない
    #逆にKが偶数ならマンハッタン距離が偶数の任意の点に行ける
    #K:奇数なら理論上どこでも行ける
    #よってこれ以外のパターンは全部可能
    #(0,0)->(2n+1,0)->(n+1,n+1)->(1,0)
#K:奇数のとき、移動回数と距離がmod2 で合同
def searcheven(x,y):
    if abs(x)+abs(y)>2*K:
        return None
    if (abs(x)+abs(y))%2==1:
        return None
    for ps in itertools.product([-1,1],repeat=4):
        p1,p2,p3,p4=ps
        if p1*p4==p2*p3:
            if p3*(K-p1*x-p2*y)==-p1*K:
                a,b=0,p4*K
                if abs(x-a)+abs(y-b)==K and abs(a)+abs(b)==K:
                    return (a,b)
                a,b=p3*K,0
                if abs(x-a)+abs(y-b)==K and abs(a)+abs(b)==K:
                    return (a,b)
            else:
                pass
        else:
            tmp1=K-p1*x-p2*y
            tmp2=K
            tmp3=p4*tmp1+p2*tmp2
            tmp4=-p3*tmp1-p1*tmp2
            det=-p1*p4+p2*p3
            a,b=(tmp3//det,tmp4//det)
            if abs(x-a)+abs(y-b)==K and abs(a)+abs(b)==K:
                return (a,b)
            else:
                pass
    return None

ans=[(0,0)]
while(True):
    nx,ny=ans[-1]
    if abs(nx-X)+abs(ny-Y)<2*K:
        if (abs(nx-X)+abs(ny-Y))%2==0:
            p,q=searcheven(X-nx,Y-ny)
            ans.append((p+nx,q+ny))
            ans.append((X,Y))
            break
        else:
            if len(ans)>1:
                tmp=searcheven(ans[-2])
                if tmp!=None:
                    ans.pop()
                    ans.append(tmp)
                    ans.append((X,Y))
                    break
            tmpx=K//2
            tmpy=K-tmpx
            nextkouho=[(tmpx,tmpy),(tmpx,-tmpy),(-tmpx,tmpy),(-tmpx,-tmpy),(K,0),(-K,0),(0,K),(0,-K)]
            for point in nextkouho:
                ptmp,qtmp=point
                p=ptmp+nx;q=qtmp+ny
                if abs(X-p)+abs(Y-q)<=2*K:
                    ans.append((p,q))
                    break
    elif abs(nx)+K<=abs(X):
        if X<0:
            ans.append((nx-K,ny))
            continue
        else:
            ans.append((nx+K,ny))
            continue
    elif abs(ny)+K<=abs(Y):
        if Y<0:
            ans.append((nx,ny-K))
            continue
        else:
            ans.append((nx,ny+K))
            continue


#print(ans)
s=len(ans)-1
flag=1
for i in range(s):
    ax,ay=ans[i]
    bx,by=ans[i+1]
    if abs(ax-bx)+abs(ay-by)==K:
        pass
    else:
        flag=0
        break
if flag==0:
    print("NG")
print(s)
for i in range(1,s+1):
    print(ans[i][0],ans[i][1])

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b > 0:
        (a, b) = (b, a % b)
    return a

def whethrepunit(X,u,start=0):
    n = len(u)
    k = len(X)
    for i in range(len(X)):
        if X[(i+start)%k] != u[i%n]:
            return False
    else:
        return True

s = input()
t = input()
M = len(s)
N = len(t)
MNgcd = gcd(M,N)
for i in range(1,MNgcd+1):
    if MNgcd % i:
        continue
    else:
        un = s[:i]
        t_start = (t*2).find(un)
        if t_start < 0:
            continue
        if whethrepunit(s,un) == False:
            continue
        if whethrepunit(t,un,t_start) == False:
            continue
        print(-1)
        exit()
else:
    tt = t*2
    z = len(tt)//len(s)
    ans = 0
    for i in range(z+1):
        p = tt.find(1,s*i)
        if p < 0:
            break
    print(i-1)