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: Time Limit Exceeded

Solution code:
import sys
 
def main():
    s = sys.stdin.buffer.readline().rstrip()
    t = sys.stdin.buffer.readline().rstrip()
 
    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3
 
    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if u not in s:
            hi = mi
        else:
            lo = mi + 1
 
    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return
 
    print(lo - 1)
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
input = raw_input
 
def main():
    s = input()
    t = input()
 
    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3
 
    lo, hi = 0, (len(s) + len(t) - 1) // len(t)
    while lo < hi:
        mi = (lo + hi) // 2
        u = mi * t
        if u not in s:
            hi = mi
        else:
            lo = mi + 1
 
    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return
 
    print(lo - 1)

 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    BASE = 10**9 + 7
    MOD = 2**31 - 1  # メルセンヌ素数

    # [Ssの先頭lenRH文字]のハッシュ値を求める
    def getHash(Ss, lenRH):
        hashS = 0
        for S in Ss[:lenRH]:
            hashS *= BASE
            hashS += ord(S)
            hashS %= MOD
        return hashS

    ss = input()
    ts = input()

    cs = set(ss)
    ct = set(ts)
    if len(cs) == 1 and len(ct) == 1 and cs == ct:
        print(-1)
        return

    Ss = ss + ss
    lenS, lenT = len(Ss), len(ts)
    lenRH = lenT

    powB_P = pow(BASE, lenRH)

    hashS = getHash(Ss, lenRH)
    hashT = getHash(ts, lenRH)

    isFounds = [False] * lenS

    Ss += '$' # ダミー
    for i in range(lenS - lenRH + 1):
        # ハッシュ値が一致
        if hashS == hashT:
            isFounds[i] = True
        hashS *= BASE
        hashS += ord(Ss[i+lenRH]) - ord(Ss[i])*powB_P
        hashS %= MOD
#    print(isFounds)

    ans = 0
    for i in range(lenS):
        if not isFounds[i]: continue
        num = 0
        for j in range(i, lenS, lenT):
            if isFounds[j]:
                num += 1
                isFounds[j] = False
            else:
                break
#        ans = max(ans, num)
        if num > ans:
            ans = num

    if lenS % lenT == 0 and ans == lenS//lenT:
        print(-1)
    else:
        print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve(s, t):
    ok=1
    while True:
        if t*ok not in s:
            ng = ok
            ok = ng>>1
            break
        ok <<= 1
    if ng == 1:
        return 0
    while ok+1 < ng:
        c = (ok+ng)>>1
        if t*c in s:
            ok = c
        else:
            ng = c
    return ok

S = input()
T = input()
nS = len(S)
nT = len(T)
S = S*((nT//nS)*3+4)
ans = solve(S, T)
if T*(ans+1) in S*2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    BASE = 10**9 + 7
    MOD = 2**61 - 1  # メルセンヌ素数

    # [Ssの先頭lenRH文字]のハッシュ値を求める
    def getHash(Ss, lenRH):
        hashS = 0
        for S in Ss[:lenRH]:
            hashS *= BASE
            hashS += ord(S)
            hashS %= MOD
        return hashS

    ss = input()
    ts = input()

    cs = set(ss)
    ct = set(ts)
    if len(cs) == 1 and len(ct) == 1 and cs == ct:
        print(-1)
        return
    elif ss.replace(ts, '') == '':
        print(-1)
        return

    Ss = ss + ss
    lenS, lenT = len(Ss), len(ts)
    lenRH = lenT

    powB_P = pow(BASE, lenRH)

    hashS = getHash(Ss, lenRH)
    hashT = getHash(ts, lenRH)

    isFounds = [False] * lenS

    Ss += '$' # ダミー
    for i in range(lenS - lenRH + 1):
        # ハッシュ値が一致
        if hashS == hashT:
            isFounds[i] = True
        hashS *= BASE
        hashS += ord(Ss[i+lenRH]) - ord(Ss[i])*powB_P
        hashS %= MOD
#    print(isFounds)

    ans = 0
    for i in range(lenS):
        if not isFounds[i]: continue
        num = 0
        for j in range(i, lenS, lenT):
            if isFounds[j]:
                num += 1
                isFounds[j] = False
            else:
                break
        ans = max(ans, num)

    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
s*=(len(t)+len(s)-1)//len(s)
ans=0
S=s*3
ind=0
for i in range(1,3*len(s)//len(t)):
    if t*i in S[ind:]:
        ans=i
        ind=S.find(t*i)
S=s*4
ind=0
num=0
for i in range(1,4*len(s)//len(t)):
    if t*i in S[ind:]:
        num=i
        ind=S.find(t*i)
if num>ans:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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()
    t = input()

    if len(s) < len(t):
        s *= (len(t) + len(s) - 1) // len(s)
    n = len(s)
    s *= 3

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

    if len(t * (lo - 1)) >= 2 * n:
        print(-1)
        return

    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: Time Limit Exceeded

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

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

S,T

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

MOD = 10 ** 16 + 61
base = 12345
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)
    for i,s in enumerate(S):
        ret[i] = (ret[i-1] + power[i] * ord(s)) % MOD
    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)]

INF = 10 ** 18
visited = [False] * LS
dp = [None] * LS

arr = [INF] * LS

q = [(i,0) for i,bl in enumerate(can_start) if not bl]

while q:
    qq = []
    for x,d in q:
        if arr[x] == INF:
            arr[x] = d
            qq.append(((x-LT)%LS, d+1))
    q = qq

answer = max(arr)

if answer >= INF:
    answer = -1

print(answer)

Submission status: Time Limit Exceeded

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)]

INF = 10 ** 18
visited = [False] * LS
dp = [None] * LS

def dfs(i):
    if visited[i]:
        if dp[i] is None:
            # ループ
            return INF
        return dp[i]
    visited[i] = True
    if not can_start[i]:
        dp[i] = 0
        return 0
    x = dfs((i + LT) % LS) + 1
    dp[i] = x
    return x

answer = max(dfs(i) for i in range(LS))

if answer >= INF:
    answer = -1

print(answer)

Submission status: Time Limit Exceeded

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

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

S,T

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

MOD = 10 ** 16 + 61
base = 12345
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)
    for i,s in enumerate(S):
        ret[i] = (ret[i-1] + power[i] * ord(s)) % MOD
    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)]

INF = 10 ** 18
visited = [False] * LS
dp = [None] * LS

def dfs(i):
    if visited[i]:
        if dp[i] is None:
            # ループ
            return INF
        return dp[i]
    visited[i] = True
    if not can_start[i]:
        dp[i] = 0
        return 0
    x = dfs((i + LT) % LS) + 1
    dp[i] = x
    return x

answer = max(dfs(i) for i in range(LS))

if answer >= INF:
    answer = -1

print(answer)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def z_algo(S):  # [z_algo, "i8[:](i8[:])"],
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証1: https://atcoder.jp/contests/abc150/submissions/15829530
    # 検証2: https://atcoder.jp/contests/abc141/submissions/15855247
    i, j, n = 1, 0, len(S)
    Z = np.zeros(S.shape, dtype=np.int64)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(s, t):
    ns = len(s)
    nt = len(t)
    n = max(ns, nt) * 2
    ts = np.empty(n*4, dtype=np.int64)
    ts[:n*2] = t[np.arange(2*n, dtype=np.int64) % nt]
    ts[n*2:] = s[np.arange(2*n, dtype=np.int64) % ns]
    Z = z_algo(ts)
    ma = Z[n*2:].max()
    if ma > n:
        return -1
    else:
        return ma // nt

numba_compile([
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8(i1[:],i1[:])"],
])

def main():
    s = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    t = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    ans = solve(s, t)
    print(ans)

main()

Submission status: Accepted

Solution code:
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
    depth_list = [-1] * len(S)
    for n in location_list:
        if depth_list[n] >= 0:
            continue
        cur_node = n
        d, has_loop = 0, False
        while node_flag_list[cur_node] == 1:
            depth_list[cur_node] = d
            d += 1
            cur_node = (cur_node + len(T)) % len(S)
            if cur_node == n:
                has_loop = True
                break
        if has_loop:
            print(-1)
            return

    print(max(depth_list) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
import random

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列


    class rh:#base,max_n,convertを指定すること
        def __init__(self,base=26,max_n=5*10**5):#baseとmaxnを指定すること。baseは偶数(modが奇数)
            self.mod=random.randrange(1<<54-1,1<<55-1,2)#奇数、衝突させられないよう乱数で生成
            self.base=int(base*0.5+0.5)*2#偶数,英小文字なら26とか
            self.max_n=max_n
            self.pows1=[1]*(max_n+1)
            cur1=1
            for i in range(1,max_n+1):
                cur1=cur1*base%self.mod
                self.pows1[i]=cur1
    
        def convert(self,c): return alp2num(c,False)#大文字の場合Trueにする
        
        def get(self, s):#特定の文字のhash. O(|s|)
            n=len(s)
            mod=self.mod
            si=[self.convert(ss) for ss in s]
            h1=0
            for i in range(n):h1=(h1+si[i]*self.pows1[n-1-i])%mod
            return h1
        
        def get_roll(self, s, k):#ローリングハッシュ,特定の文字の中から長さkのhashをすべて得る,O(|s|)
            n=len(s)
            si=[self.convert(ss) for ss in s]
            mod=self.mod
            h1=0
            for i in range(k):h1=(h1+si[i%n]*self.pows1[k-1-i])%mod
            hs=[0]*n
            hs[0]=h1
            mbase1=self.pows1[k]
            base=self.base
            for i in range(1,n): 
                front=si[i-1];back=si[(i+k-1)%n]
                h1=(h1*base-front*mbase1+back)%mod
                hs[i]=h1
            return hs
    
    s=input()
    t=input()
    n=len(s)
    nt=len(t)
    rhs=rh()
    has=rhs.get(t)
    hass=rhs.get_roll(s,nt)
    l=[hass[i]==has for i in range(n)]
    ds=[0]*n
    for i in range(n):
        ci=i
        q=deque()
        while l[ci] and ds[ci]==0:
            q.append(ci)
            ci=(ci+nt)%n
            if ci==i:
                print(-1)
                return
        tot=ds[ci]
        while q:
            tot+=1
            ci=q.pop()
            ds[ci]=tot
    print(max(ds))
        




if __name__ == "__main__":
    
    main()

Submission status: Accepted

Solution code:
# AOJ ALDS1_14_B "String Search"
# returns i s.t. S[i+j] = T[j] for 0 <= j < len(T)

def RollingHash(S, T, ls):
    if len(S) < len(T):
        return []
    # gcd(h, b) = 1
    h = 10**11+7
    b = 10**7+7
    L = len(T)

    bL = 1
    for i in range(L):
        bL = bL * b % h

    hashS = 0
    for i in range(L):
        hashS = (hashS * b + S[i]) % h

    hashT = 0
    for i in range(L):
        hashT = (hashT * b + T[i]) % h
    
    correctIndexes = [0]*len(S)
    ret = 0
    if hashS == hashT:
        correctIndexes[0] = 1
    for j in range(len(S)-L):
        hashS = (hashS * b - S[j]*bL + S[L+j]) % h
        if hashS == hashT:
            tmp = correctIndexes[j+1-L] + 1
            correctIndexes[j+1] = tmp
            if tmp > ret: ret = tmp
    if ret*L > 2*ls:
        return -1
    return ret


import sys
input = sys.stdin.buffer.readline

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

ls = len(S)
lt = len(T)
S = S*((2*lt+3*ls-1)//ls)
ans = RollingHash(S, T, ls)
print(ans)

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # 参考 (https://qiita.com/b1ueskydragon/items/41cec5d36c747f73d515)
    def KMP(S, word):
        def partial_match_table(word):
            table = [0] * (len(word) + 1)
            table[0] = -1
            i, j = 0, 1

            while j < len(word):
                matched = word[i] == word[j]

                if not matched and i > 0:
                    i = table[i]
                else:
                    if matched:
                        i += 1
                    j += 1
                    table[j] = i

            return table

        table = partial_match_table(word)
        # print(table)
        i, p = 0, 0
        match = []
        while (i < len(S) and p < len(word)):
            # print(i,p)
            if S[i] == word[p]:
                i += 1;
                p += 1
                if p == len(word):
                    match.append(i - p)
                    p = table[p]
            else:
                if p == 0:
                    i += 1
                else:
                    p = table[p]

        return match

    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def reset(self):
            self.parent = [-1] * len(self.parent)

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}

    S = SI()
    T = SI()
    if len(S)<len(T):
        S *= (len(T)//len(S))+1
    #print(S)
    N = len(S)
    n = len(T)
    V = [[]for _ in range(N)]
    S *= 2
    kmp = KMP(S,T)
    #print(kmp)

    for i in kmp:
        if i>=N:
            continue
        V[i%N].append((i+n)%N)
    uf = UnionFind(N)
    #print(V)

    def dfs(s):
        cnt = 0
        for v in V[s]:
            # 一回見た中に自身が含まれている
            if uf.same(s,v):
                return -1
            # すでに一回は見た頂点の場合
            if uf.size(v)>1:
                #print("test",s,uf.size(v))
                cnt = uf.size(v)
                uf.unite(s, v)
                return cnt
            else:
                uf.unite(s, v)
                child = dfs(v)
            if child==-1:
                return -1
            cnt = child+1
        return cnt

    ans = 0
    for i in range(N):
        if uf.size(i)!=1:
            continue
        cur = dfs(i)
        #print(cur,i)
        if cur==-1:
            print(-1)
            return
        if ans<cur:
            ans = cur
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examF()

"""
abababababc
babababa
"""

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    left = 0  # 左の箱の左端(本当はここでので宣言は不要だけど理解の為)
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 箱の幅が0だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
        left = 0  # これも本当は不要
    return lcp

def dfs(i,si):
    dp[i]=0
    ni=(i+tn)%sn
    if lcp[tn+1+ni]!=tn:return False
    if ni==si:return True
    if dp[ni]==-1 and dfs(ni,si):return True
    dp[i]=dp[ni]+1

s=SI()
t=SI()
ss = s
while len(ss) < len(s) + len(t): ss += s
lcp = LcpByZ(t + "@" + ss)
sn = len(s)
tn = len(t)
dp=[-1]*sn
for i in range(sn):
    if dp[i]!=-1:continue
    if dfs(i,i):
        print(-1)
        exit()
print(max(dp))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens + lent) * 2
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent * 2 - 1:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-1
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    t = SI()
    lens = len(s)
    lent = len(t)

    def cx(x):
        return ord(x) - ord('a') + 1

    hsh = 0
    for x in t:
        hsh = (hsh * 26 + cx(x)) % MOD

    n = (lens+lent) * 2 + 1
    dp = [0] * n

    h = 0
    ans = 0
    for i in range(n):
        if i >= lent:
            h -= cx(s[(i - lent)%lens]) * pow(26,lent-1,MOD)
        h = (h * 26 + cx(s[i % lens])) % MOD
        if h == hsh:
            if i < lent:
                dp[i] = 1
            else:
                dp[i] = dp[i-lent] + 1
            ans = max(ans,dp[i])

    if n - ans * lent < lent * 2:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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]
inv = [0] * n
for i in range(n):
    if l[i]:
        t = (i + m) % n
        i = t
        inv[t] += 1
ans = 0
v = [0] * n
for i in range(n):
    if inv[i] == 0:
        v[i] = 1
        r = 0
        while l[i]:
            r += 1
            t = (i + m) % n
            v[t] = 1
            i = t
        ans = max(ans, r)
if 0 in v:
    print(-1)
else:
    print(ans)