Problem:


Score : 600 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.

There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s.

Notes

A string a is a substring of another string b if and only if there exists an integer x (0 \leq x \leq |b| - |a|) such that, for any y (1 \leq y \leq |a|), a_y = b_{x+y} holds.

We assume that the concatenation of zero copies of any string is the empty string. From the definition above, the empty string is a substring of any string. Thus, for any two strings s and t, i = 0 satisfies the condition in the problem statement.

Constraints

1 \leq |s| \leq 5 \times 10^5

1 \leq |t| \leq 5 \times 10^5

s and t consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i; if the number is infinite, print -1.

Sample Input 1

abcabab
ab

Sample Output 1

3

The concatenation of three copies of t, ababab, is a substring of the concatenation of two copies of s, abcabababcabab, so i = 3 satisfies the condition.

On the other hand, the concatenation of four copies of t, abababab, is not a substring of the concatenation of any number of copies of s, so i = 4 does not satisfy the condition.

Similarly, any integer greater than 4 does not satisfy the condition, either. Thus, the number of non-negative integers i satisfying the condition is finite, and the maximum value of such i is 3.

Sample Input 2

aa
aaaaaaa

Sample Output 2

-1

For any non-negative integer i, the concatenation of i copies of t is a substring of the concatenation of 4i copies of s. Thus, there are infinitely many non-negative integers i that satisfy the condition.

Sample Input 3

aba
baaab

Sample Output 3

0

As stated in Notes, i = 0 always satisfies the condition.



Sample input:
abcabab
ab


Sample output:
3

Submission status: Wrong Answer

Solution code:
#!/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
    S2 = S2 * 1000
    T2 = T * 800

    if T2 in S2:
        return -1

    ans = 0
    for i in range(300):
        T3 = T * i
        if T3 in S2:
            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))
# S = randomString(100000)
# T = randomString(100000)

print(solve_slow(S, T))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    s = input()
    s += s

    t = input()
    lo, hi = 0, len(s) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if u not in s:
            hi = mi
        else:
            lo = mi + 1
    print(lo - 1)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
ss = s*(len(t)//len(s)+1)*2
ssss = ss*2
c = ss.count(t)

for i in range(c+2) :
    if t*i not in ssss :
        print(i-1)
        break
else :
    print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

s = input()
t = input()

a = (len(t)+len(s)-1)//len(s)
s = s*a

def findt(s):
    l = len(t)
    s = s.replace(t,"T")
#    print(s)
    res = 0
    ans = 0
    for i in s:
        if i == "T":
            res += 1
            ans = max(ans,res)
        else:
            res = 0
#        print(res)
    return ans

a = findt(s*2)
b = findt(s*3)

if a == b:
    print(a)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    # N = int(input())
    s = input().strip()
    t = input().strip()
    # a, b = map(int, input().split())
    # a = list(map(int, input().split()))
    # a = [int(input()) for i in range(N)]
    set_s = set(list(s))
    set_t = set(list(t))
    if len(set_s) == 1 and len(set_t) == 1:
        if s[0] == t[0]:
            print(-1)
            return
    while len(s) < len(t):
        s += s
    len_s = len(s)
    len_t = len(t)
    ts = s
    tt = t
    ok = False
    while True:
        if ts[0:len(tt)] == tt:
            ts = ts[len(tt):]
            if len(ts) == 0:
                ok = True
                break
            if len(ts) < len(tt):
                tmp = tt
                tt = ts
                ts = tmp
        else:
            break
    if ok:
        print(-1)
        return
    left = 0
    right = 0
    i = 0
    # print("left")
    for i in range(0, len_s, len_t):
        # print(i, i+len_t-1)
        # print(s[i:i+len_t])
        if s[i:i+len_t] == t:
            left += 1
        else:
            break
    # print(i)
    if i == len_s:
        print(-1)
    else:
        # print("right")
        for i in range(len_s, -1, -len_t):
            # print(s[i-len_t:i])
            if s[i-len_t:i] == t:
                right += 1
            else:
                break
        # print(left, right)
        print(left+right)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
res = input()
s = res*3
t = input()
if res in t:
    print(-1)
    exit()
most = 0
for i in range(1, len(s)):
    if t*i in s:most=i
print(most)

Submission status: Wrong Answer

Solution code:
s=input().rstrip()
A=len(s)
s=s*2;
t=input().rstrip()
x=list(s)
y=list(t)
if len(list(set(x)))==1 and len(list(set(y)))==1:
    print(-1)
else:
    while(len(s)<len(t)):
        s=s*2;
    x=list(s)
    i=0;
    B=0;
    N=[]
    #print(x)
    while(i<len(x)-len(y)+1):
        T=x[i:i+len(y)]
        #print(T)
        if ''.join(T)==t:
            B+=1;
            i+=len(y)
        else:
            N.append(B)
            B=0;
            i+=1;
    N.append(B)
    if max(N)==A:
        print(-1)
    else:
        print(max(N))

Submission status: Wrong Answer

Solution code:
import sys

def main():
    S = sys.stdin.readline().rstrip()
    T = sys.stdin.readline().rstrip()

    ls = len(S)
    lt = len(T)

    SS = S*5
    TT = T*5

    if S in TT and T in SS:
        print(-1)
        sys.exit()

    if ls < lt:
        bai = lt // ls
        S *= bai
        ls = len(S)

    S *= 5
    count = 1
    while True:
        TT = T * count
        if TT in S:
            count += 1
        else:
            print(count-1)
            break

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def z(s):
    n = len(s)
    z = [0] * n
    if n == 0:
        return z
    z[0] = n
    i = 1
    l = 0
    r = 0
    while i < n:
        if r >= i and z[i-l] < r-i+1:
            z[i] = z[i-1]
        else:
            l = i
            if r < i: r = i
            while r < n and s[r-l] == s[r]:
                r += 1
            z[i] = r-l
            r -= 1
        i += 1
    return z

s = ns()
t = ns()

zs = z(s)
zt = z(t)
zst = z(t+s+s)

pes = len(s)
for i in range(1, len(s)):
    if len(s) % i == 0 and zs[i] >= len(s)-i:
        pes = i
        break

pet = len(t)
for i in range(1, len(t)):
    if len(t) % i == 0 and zt[i] >= len(t)-i:
        pet = i
        break

if pes % pet == 0:
    for i in range(pet):
        if zst[len(t)+i] >= pes:
            print(-1)
            sys.exit(0)

lt = len(t)
m = s + s
while len(m) <= 2*len(t):
    m = m + m
while len(t) < len(m):
    t = t + t
# print(t, m, s)
zx = z(t+"$"+m)
# print(zx)
ans = max(zx[len(t)+1:])
print(ans//lt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    # N = int(input())
    s = input().strip()
    t = input().strip()
    # a, b = map(int, input().split())
    # a = list(map(int, input().split()))
    # a = [int(input()) for i in range(N)]
    set_s = set(list(s))
    set_t = set(list(t))
    if len(set_s) == 1 and len(set_t) == 1:
        if s[0] == t[0]:
            print(-1)
            exit()
    while len(s) < len(t):
        s += s
    len_s = len(s)
    len_t = len(t)
    left = 0
    right = 0
    i = 0
    # print("left")
    for i in range(0, len_s, len_t):
        # print(i, i+len_t-1)
        # print(s[i:i+len_t])
        if s[i:i+len_t] == t:
            left += 1
        else:
            break
    if i == len_s:
        print(-1)
    else:
        # print("right")
        for i in range(len_s, -1, -len_t):
            # print(s[i-len_t:i])
            if s[i-len_t:i] == t:
                right += 1
            else:
                break
        # print(left, right)
        print(left+right)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = input().rstrip()
T = input().rstrip()

# Sの方が長くする
LS = len(S)
LT = len(T)
n = (LT + (-LT) % LS) // LS
S *= (n+1)
S = S[:LS+LT]

MOD = 10 ** 9 + 7
base = 1234
base_inv = pow(base,MOD-2,MOD) 
power = [1] * (LS+LT)
power_inv = [1] * (LS+LT)
for n in range(1,LS+LT):
    power[n] = power[n-1] * base % MOD
    power_inv[n] = power_inv[n-1] * base_inv % MOD

def to_rolling_hash(S):
    ret = [0] * len(S)
    prev = 0
    for i,s in enumerate(S):
        x = (prev + power[i] * ord(s)) % MOD
        ret[i] = x
        prev = x
    return ret

S_hash = to_rolling_hash(S) + [0]
T_hash = to_rolling_hash(T)[-1] # 文字列全体

can_start = [(S_hash[i + LT - 1] - S_hash[i - 1]) * power_inv[i] % MOD == T_hash for i in range(LS)]

Submission status: Wrong Answer

Solution code:
from math import ceil
s = input()
t = input()

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

ans = 0
for i in range(1,len(s)//len(t)+1):
    if s.count(t*i) > 0:
        ans = i

if (s+s).count(t*(ans+1)) > 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def z(s):
    n = len(s)
    z = [0] * n
    if n == 0:
        return z
    z[0] = n
    i = 1
    l = 0
    r = 0
    while i < n:
        if r >= i and z[i-l] < r-i+1:
            z[i] = z[i-1]
        else:
            l = i
            if r < i: r = i
            while r < n and s[r-l] == s[r]:
                r += 1
            z[i] = r-l
            r -= 1
        i += 1
    return z

s = ns()
t = ns()

zs = z(s)
zt = z(t)
zst = z(t+s+s)

pes = len(s)
for i in range(1, len(s)):
    if len(s) % i == 0 and zs[i] >= len(s)-i:
        pes = i
        break

pet = len(t)
for i in range(1, len(t)):
    if len(t) % i == 0 and zt[i] >= len(t)-i:
        pet = i
        break

if pes % pet == 0:
    for i in range(pet):
        if zst[len(t)+i] >= pet:
            print(-1)
            sys.exit(0)

lt = len(t)
m = s + s
while len(m) <= 2*len(t):
    m = m + m
while len(t) < len(m):
    t = t + t
# print(t, m, s)
zx = z(t+"$"+m)
# print(zx)
ans = max(zx[len(t)+1:])
print(ans//lt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    # N = int(input())
    s = input().strip()
    t = input().strip()
    # a, b = map(int, input().split())
    # a = list(map(int, input().split()))
    # a = [int(input()) for i in range(N)]
    set_s = set(list(s))
    set_t = set(list(t))
    if len(set_s) == 1 and len(set_t) == 1:
        if s[0] == t[0]:
            print(-1)
            exit()
    while len(s) < len(t):
        s += s
    len_s = len(s)
    len_t = len(t)
    left = 0
    right = 0
    i = 0
    # print("left")
    for i in range(0, len_s, len_t):
        # print(s[i:i+len_t])
        if s[i:len_t] == t:
            left += 1
        else:
            break
    if i == len_s:
        print(-1)
    else:
        # print("right")
        for i in range(len_s, -1, -len_t):
            # print(s[i-len_t:i])
            if s[i-len_t:i] == t:
                right += 1
            else:
                break
        print(left+right)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = LS2()
s = len(S)
for i in range(s):
    S[i] = ord(S[i])-97

T = LS2()
t = len(T)
for i in range(t):
    T[i] = ord(T[i])-97


def f(mod,base):

    A = [1]  # A[i] = base**i
    for _ in range(1,max(s,t)+1):
        A.append((A[-1]*base) % mod)

    B = [1]  # B[i] = base**(t*i)
    for _ in range(1,s+1):
        B.append((B[-1]*A[t]) % mod)

    c = pow(A[t]-1,mod-2,mod)  # (base**t-1)**(-1)
    d = pow(A[s]-1,mod-2,mod)  # (base**s-1)**(-1)

    def g(n):  # Tをn個連結したものは、Sをいくつか連結したものの部分文字列になりうるか
        a = 0  # Tをn個連結したもののHash値
        for i in range(t):
            a += T[i]*A[t-1-i]
            a %= mod
        a *= (B[n]-1)*c
        a %= mod

        H = [0]  # H[i] = Sの左i文字を結合した文字列のHash値
        for i in range(s):
            H.append((H[-1]*base+S[i]) % mod)

        b = H[-1]  # SのHash値

        def h(m):  # Sを無限個繋げた文字列の、左m文字を結合した文字列のHash値
            q,r = m//s,m % s
            res = b
            res *= pow(A[s],q,mod)-1
            res %= mod
            res *= d
            res %= mod
            res *= A[r]
            res += H[r]
            res %= mod
            return res

        for i in range(s):
            x = h(i+t*n)-h(i)*B[n]
            x %= mod
            if x == a:
                return True
        return False

    left = 0  # ok
    right = s+1  # ng
    while left + 1 < right:
        mid = (left + right)//2
        if g(mid):
            left = mid
        else:
            right = mid
    print(left if left != s else -1)


f(10**9+7,1234)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = LS2()
s = len(S)
for i in range(s):
    S[i] = ord(S[i])-97

T = LS2()
t = len(T)
for i in range(t):
    T[i] = ord(T[i])-97


def f(mod,base):

    A = [1]  # A[i] = base**i
    for _ in range(1,max(s,t)+1):
        A.append((A[-1]*base) % mod)

    B = [1]  # B[i] = base**(t*i)
    for _ in range(1,s+1):
        B.append((B[-1]*A[t]) % mod)

    d = pow(A[t]-1,mod-2,mod)  # (base**t-1)**(-1)
    e = pow(A[s]-1,mod-2,mod)  # (base**s-1)**(-1)

    def g(n):  # Tをn個連結したものは、Sをいくつか連結したものの部分文字列になりうるか
        a = 0  # Tをn個連結したもののHash値
        for i in range(t):
            a += T[i]*A[t-1-i]
            a %= mod
        a *= B[n]-1
        a %= mod
        a *= d
        a %= mod

        H = [0]  # H[i] = Sの左i文字を結合した文字列のHash値
        for i in range(s):
            H.append((H[-1]*base+S[i]) % mod)

        b = H[-1]  # SのHash値

        def h(m):  # Sを無限個繋げた文字列の、左m文字を結合した文字列のHash値
            q,r = m//s,m % s
            res = b
            res *= pow(A[s],q,mod)-1
            res %= mod
            res *= e
            res %= mod
            res *= A[r]
            res += H[r]
            res %= mod
            return res

        for i in range(s):
            x = h(i+t*n)-h(i)*B[n]
            x %= mod
            if x == a:
                return True
        return False

    left = 0  # ok
    right = s+1  # ng
    while left + 1 < right:
        mid = (left + right)//2
        if g(mid):
            left = mid
        else:
            right = mid
    print(left if left != s else -1)

def main():
    f(10**9+7,1234)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = LS2()
s = len(S)
for i in range(s):
    S[i] = ord(S[i])-97

T = LS2()
t = len(T)
for i in range(t):
    T[i] = ord(T[i])-97


def f(mod,base):

    A = [1]  # A[i] = base**i
    for _ in range(1,max(s,t)+1):
        A.append((A[-1]*base) % mod)

    B = [1]  # B[i] = base**(t*i)
    for _ in range(1,s+1):
        B.append((B[-1]*A[t]) % mod)

    d = pow(A[t]-1,mod-2,mod)  # (base**t-1)**(-1)
    e = pow(A[s]-1,mod-2,mod)  # (base**s-1)**(-1)

    def g(n):  # Tをn個連結したものは、Sをいくつか連結したものの部分文字列になりうるか
        a = 0  # Tをn個連結したもののHash値
        for i in range(t):
            a += T[i]*A[t-1-i]
            a %= mod
        a *= B[n]-1
        a %= mod
        a *= d
        a %= mod

        H = [0]  # H[i] = Sの左i文字を結合した文字列のHash値
        for i in range(s):
            H.append((H[-1]*base+S[i]) % mod)

        b = H[-1]  # SのHash値

        def h(m):  # Sを無限個繋げた文字列の、左m文字を結合した文字列のHash値
            q,r = m//s,m % s
            res = b
            res *= pow(A[s],q,mod)-1
            res %= mod
            res *= e
            res %= mod
            res *= A[r]
            res += H[r]
            res %= mod
            return res

        for i in range(s):
            x = h(i+t*n)-h(i)*B[n]
            x %= mod
            if x == a:
                return True
        return False

    left = 0  # ok
    right = s+1  # ng
    while left + 1 < right:
        mid = (left + right)//2
        if g(mid):
            left = mid
        else:
            right = mid
    print(left if left != s else -1)


f(10**9+7,1234)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = LS2()
s = len(S)
for i in range(s):
    S[i] = ord(S[i])-97

T = LS2()
t = len(T)
for i in range(t):
    T[i] = ord(T[i])-97


def f(mod,base):

    A = [1]  # A[i] = base**i
    for _ in range(1,max(s,t)+1):
        A.append((A[-1]*base) % mod)

    def g(n):  # Tをn個連結したものは、Sをいくつか連結したものの部分文字列になりうるか
        a = 0  # Tをn個連結したもののHash値
        for i in range(t):
            a += T[i]*A[t-1-i]
            a %= mod
        a *= pow(A[t],n,mod)-1
        a %= mod
        a *= pow(A[t]-1,mod-2,mod)
        a %= mod

        H = [0]  # H[i] = Sの左i文字を結合した文字列のHash値
        for i in range(s):
            H.append((H[-1]*base+S[i]) % mod)

        b = H[-1]  # SのHash値

        def h(m):  # Sを無限個繋げた文字列の、左m文字を結合した文字列のHash値
            q,r = m//s,m % s
            res = b
            res *= pow(A[s],q,mod)-1
            res %= mod
            res *= pow(A[s]-1,mod-2,mod)
            res %= mod
            res *= A[r]
            res += H[r]
            res %= mod
            return res

        for i in range(s):
            x = h(i+t*n)-h(i)*pow(A[t],n,mod)
            x %= mod
            if x == a:
                return True
        return False

    left = 0  # ok
    right = s+1  # ng
    while left + 1 < right:
        mid = (left + right)//2
        if g(mid):
            left = mid
        else:
            right = mid
    print(left if left != s else -1)


f(10**9+7,1234)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = LS2()
s = len(S)
for i in range(s):
    S[i] = ord(S[i])-97

T = LS2()
t = len(T)
for i in range(t):
    T[i] = ord(T[i])-97


def f(mod,base):

    A = [1]  # A[i] = base**i
    for _ in range(1,max(s,t)+1):
        A.append((A[-1]*base) % mod)

    def g(n):  # Tをn個連結したものは、Sをいくつか連結したものの部分文字列になりうるか
        a = 0  # Tをn個連結したもののHash値
        for i in range(t):
            a += T[i]*A[i]
            a %= mod
        a *= pow(A[t],n,mod)-1
        a %= mod
        a *= pow(A[t]-1,mod-2,mod)
        a %= mod

        H = [0]  # H[i] = Sの左i文字を結合した文字列のHash値
        for i in range(s):
            H.append((H[-1]+S[i]*A[i]) % mod)

        b = H[-1]  # SのHash値

        def h(m):  # Sを無限個繋げた文字列の、左m文字を結合した文字列のHash値
            q,r = m//s,m % s
            res = b
            res *= pow(A[s],q,mod)-1
            res %= mod
            res *= pow(A[s]-1,mod-2,mod)
            res %= mod
            res += H[r]*pow(A[s],q,mod)
            res %= mod
            return res

        for i in range(s):
            x = h(i+t*n)-h(i)
            x *= pow(A[i],mod-2,mod)
            x %= mod
            if x == a:
                return True
        return False

    left = 0  # ok
    right = s+1  # ng
    while left + 1 < right:
        mid = (left + right)//2
        if g(mid):
            left = mid
        else:
            right = mid
    print(left if left != s else -1)


f(10**9+7,1234)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = LS2()
s = len(S)
for i in range(s):
    S[i] = ord(S[i])-97

T = LS2()
t = len(T)
for i in range(t):
    T[i] = ord(T[i])-97


def f(mod,base):
    def g(n):  # Tをn個連結したものは、Sをいくつか連結したものの部分文字列になりうるか
        a = 0  # Tをn個連結したもののHash値
        for i in range(t):
            a += T[i]*pow(base,i,mod)
            a %= mod
        a *= pow(base,t*n,mod)-1
        a %= mod
        a *= pow(pow(base,t,mod)-1,mod-2,mod)
        a %= mod

        H = [0]  # H[i] = Sの左i文字を結合した文字列のHash値
        for i in range(s):
            H.append((H[-1]+S[i]*pow(base,i,mod)) % mod)

        b = H[-1]  # SのHash値

        def h(m):  # Sを無限個繋げた文字列の、左m文字を結合した文字列のHash値
            q,r = m//s,m % s
            res = b
            res *= pow(base,s*q,mod)-1
            res %= mod
            res *= pow(pow(base,s,mod)-1,mod-2,mod)
            res %= mod
            res += H[r]*pow(base,s*q,mod)
            res %= mod
            return res

        for i in range(s):
            x = h(i+t*n)-h(i)
            x *= pow(base,i*(mod-2),mod)
            x %= mod
            if x == a:
                return True
        return False

    left = 0  # ok
    right = s+1  # ng
    while left + 1 < right:
        mid = (left + right)//2
        if g(mid):
            left = mid
        else:
            right = mid
    print(left if left != s else -1)


f(10**9+7,1234)

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10**6)


def z_alg(S):
    N = len(S)
    Z = [0] * N
    Z[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z


def main():
    S = input()
    T = input()
    REP_S = ''
    target_len = len(S) + len(T) - 1
    while len(REP_S) < target_len:
        REP_S += S

    # Z-algorithmでREP_S中に含まれるTの場所を調べる
    T_REP_S = T + REP_S
    z = z_alg(T_REP_S)
    location_list = list()
    for i in range(len(S)):
        if z[i + len(T)] >= len(T):
            location_list.append(i)

    # Tがなければ0を出力して終了
    if len(location_list) == 0:
        print(0)
        return

    # グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
    node_flag_list = [0] * len(S)
    for n in location_list:
        node_flag_list[n] = 1
    node_num_list = [-1] * len(S)

    def dfs(node, depth=0):
        # return (has_loop, node_num)
        if depth > len(location_list):
            return True, -1
        if node_num_list[node] >= 0:
            return False, node_num_list[node]
        next_node = (node + len(T)) % len(S)
        if node_flag_list[next_node] == 0:
            node_num_list[node] = 0
            return False, 0
        has_loop, node_num = dfs(next_node, depth + 1)
        if has_loop:
            return True, -1
        node_num_list[node] = 1 + node_num
        return False, 1 + node_num

    for n in location_list:
        has_loop, _ = dfs(n)
        if has_loop:
            print(-1)
            return

    print(max(node_num_list) + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
S = input().rstrip()
T = input().rstrip()

def z_algorithm(s):
    N = len(s)
    ret = [0]*N
    ret[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + ret[k]<j:
            ret[i+k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

def solve():
    ls,lt = len(S),len(T)
    ns = 0--(lt+ls)//ls

    za = z_algorithm(T + '#' + S*ns)

    from fractions import gcd
    g = gcd(ls,lt)
    uf = UnionFind(ls)
    match = False
    for i in range(ls):
        if za[lt+1+i] == lt:
            match = True
            j = (i+lt) % ls
            if uf.is_same(i,j):
                if uf.size(i) == ls//g:
                    print(-1)
                    exit()
                continue
            uf.unite(i,j)
    if not match:
        print(0)
        exit()

    ans = 0
    for i in range(ls):
        ans = max(ans, uf.size(i)-1)
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()

def z_algorithm(s):
    N = len(s)
    ret = [0]*N
    ret[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + ret[k]<j:
            ret[i+k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

def solve():
    ls,lt = len(S),len(T)
    ns = 0--(lt+ls)//ls

    za = z_algorithm(T + '#' + S*ns)

    from fractions import gcd
    g = gcd(ls,lt)
    uf = UnionFind(ls)
    match = False
    for i in range(ls):
        if za[lt+1+i] == lt:
            match = True
            j = (i+lt) % ls
            if uf.is_same(i,j):
                if uf.size(i) == ls//g:
                    print(-1)
                    exit()
                continue
            uf.unite(i,j)
    if not match:
        print(0)
        exit()

    ans = 0
    for i in range(ls):
        ans = max(ans, uf.size(i)-1)
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
def construct_table(n, s):
    table = [-1] * (n + 1)
    j = -1
    for i in range(n):
        while j >= 0 and s[i] != s[j]:
            j = table[j]
        j += 1
        table[i + 1] = j
    return table


s = input()
t = input()
n = len(s)
m = len(t)
s2 = s * ((max(m, n) + m) // n + 1)
tb = construct_table(m, t)
l = [False] * n
i = 0
j = 0
while i < n:
    if t[j] != s2[i + j]:
        i += j - tb[j]
        if j > 0:
            j = tb[j]
    else:
        j += 1
        if j == m:
            l[i] = True
            i += j - tb[j]
            j = tb[j]
v = [0] * n
for i in range(n):
    tmp = i
    r = 0
    while l[i]:
        t = i
        i = (i - m) % n
        v[i] = v[t] + 1
        if i == tmp:
            print(-1)
            exit(0)
print(max(v))