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:
# https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
"""
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<nowiki>[:L[i]]</nowiki>
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


# https://snuke.hatenablog.com/entry/2014/12/03/214243
def z_algorithm(s):
    a = [0] * len(s)
    a[0] = len(s)
    i = 1
    j = 0
    while i < len(s):
        while i+j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a


def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a%b)

import sys

if __name__ == "__main__":
    s = input()
    t = input()
    n = max(2, (len(t)*2 + len(s) - 1) // len(s))
    s2 = s * n
    a = z_algorithm(s2)
    m = string_search(t, s2)
    min_cyle = len(s)
    for i, a_v in enumerate(a[1:len(s)]):
        if a_v >= len(s):
            min_cycle = i+1
            break
    print("min_cycle={}".format(min_cycle), file=sys.stderr)

    if len(m) == 0:
        print(0)
    elif len(t) % min_cycle == 0:
        print(-1)
    else:
        print(len(s) // gcd(len(s), len(t)))

Submission status: Runtime Error

Solution code:
# https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
"""
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<nowiki>[:L[i]]</nowiki>
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


# https://snuke.hatenablog.com/entry/2014/12/03/214243
def z_algorithm(s):
    a = [0] * len(s)
    a[0] = len(s)
    i = 1
    j = 0
    while i < len(s):
        while i+j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a


def gcd(a, b):
    if b == 1:
        return a
    return gcd(b, a%b)

import sys

if __name__ == "__main__":
    s = input()
    t = input()
    n = max(2, (len(t)*2 + len(s) - 1) // len(s))
    s2 = s * n
    a = z_algorithm(s2)
    m = string_search(t, s2)
    min_cyle = len(s)
    for i, a_v in enumerate(a[1:]):
        if a_v >= len(s):
            min_cycle = i+1
            break
    print("min_cycle={}".format(min_cycle), file=sys.stderr)

    if len(m) == 0:
        print(0)
    elif len(t) % min_cycle == 0:
        print(-1)
    else:
        print(len(s) // gcd(len(s), len(t)))

Submission status: Runtime Error

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        haystack の何番目に needle があるか。見つからなければ -1
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i += self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


def test(t, s):
    ret = []
    for i in range(len(s)):
        ret.append(s[i:i + len(t)] == t)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

while len(S) < len(T) * 4:
    S *= 2

kmp = KMP(T)
idx = kmp.search(S)
ans = 0
for k in range(len(T)):
    i = k
    cnt = 0
    while i < len(idx):
        if idx[i]:
            cnt += 1
        else:
            ans = max(cnt, ans)
            cnt = 0
        i += len(T)
    ans = max(cnt, ans)
if len(T) * ans > len(S) // 2:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        haystack の何番目に needle があるか。見つからなければ -1
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i += self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


def test(t, s):
    ret = []
    for i in range(len(s)):
        ret.append(s[i:i + len(t)] == t)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

while len(S) < len(T) * 4:
    S *= 2

kmp = KMP(T)
idx = kmp.search(S)
ans = 0
for k in range(len(T)):
    i = k
    cnt = 0
    while i < len(idx):
        if idx[i]:
            cnt += 1
        else:
            ans = max(cnt, ans)
            cnt = 0
        i += len(T)
    ans = max(cnt, ans)
if len(T) * ans > len(S) // 2:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
S=input()
T=input()
if(T*len(S)==S*len(T)):
  print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y]+=self.size[x]
        else:
            self.parent[y] = x
            self.size[x]+=self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
      
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
U = UnionFind(ls)
for i in range(ls):
    if is_same[i]:
        if U.same(i, (i+k)%ls):
            ans = -1
            break
        U.unite(i, (i+k)%ls)
if ans == -1:
    print(-1)
else:
    ans = max(U.get_size(i)-1 for i in range(ls))
    print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
ans = 0
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        n=len(s)
        self.__s=s
        self.__n=n
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(n+1),[0]*(n+1)
        P1,P2=[1]*(n+1),[1]*(n+1)
        for i in range(n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def hash(self,l,r):
        m1=self.__mod1; m2=self.__mod2
        assert 0<=l<=r<=self.__n
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)

def resolve():
    from math import ceil
    s=input()
    t=input()
    n=len(s)
    m=len(t)
    s=s*ceil(4*m/n)

    rhs=RollingHash(s)
    rht=RollingHash(t)
    t=rht.hash(0,m)
    uf=UnionFind(n)
    ok=[0]*n
    for i in range(n):
        if(rhs.hash(i,i+m)==rhs.hash(i+m,i+2*m)):
            if(not uf.unite(i,(i+m)%n)):
                print(-1)
                return
        if(rhs.hash(i,i+m)==t):
            ok[i]=1
    ans=0
    for i in range(n):
        if(ok[i]): ans=max(ans,uf.size(i))
    print(ans)
resolve()