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:
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_table()

    def create_table(self):
        table = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = table[j]
            j += 1
            table[i+1] = j
        self.table = table
    
    # sの各位置についてtが何文字一致するか
    def match(self, s):
        i, j, n = 0,0,len(s)
        ret = [0]*n

        while i < n:
            while i < n and j < self.n:
                if s[i] == self.pattern[j]:
                    i += 1
                    j += 1
                elif j == 0:
                    i += 1
                else:
                    j = self.table[j]
            if j == self.n:
                #print(i-j)
                ret[i - j] = True
                i = i-j+1
                j = 0
            else:
                break
        return ret



def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    # 最大は, (n-1)+m 
    # kn >= (n-1)+m
    # k >= 1 +(m-1)/n
    k = 1 + -(-(m-1)//n)
    si = s*k
    a = KMP(t)
    b = a.match(si)
    edges = [[] for i in range(n)]
    for i in range(n):
        if b[i]:
            edges[i].append((i+m)%n)
    # loopを見つける
    # start地点をすべて試す
    # 進む方向、戻る方向について別々に求める
    visited = [0]*n
    loop = False
    ans = 0
    for i in range(n):
        # 他のパスから辿られている場合
        if visited[i]:
            continue
        visited[i] = 1
        # →に進む
        cur = i
        right = 0
        while b[cur]:
            nxt = (cur + m) % n
            if visited[nxt]:
                loop = True
                break
            visited[nxt] = 1
            cur = nxt
            right += 1
        cur = i
        left = 0
        while b[(cur-m)%n]:
            nxt = (cur-m) % n
            if visited[nxt]:
                loop = True
                break
            visited[nxt] = 1
            cur = nxt
            left += 1
        if not loop:
            ans = max(ans, right+left)
        else:
            ans = -1
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
W = input()
M = len(S)
S *= 3 * (len(W)//len(S)+1)


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
p = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        p = N//d
        N = d
        break

W = W[:d]

T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W) + 1:
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1
m = 0
def KMP(i0):
    global m
    ret = -1
    i = 0

    while m + i < len(S):
        if W[i] == S[m + i]:
            i += 1
            if i == len(W):
                t = m
                m = m + i - T[i]
                if i > 0:
                    i = T[i]
                return t
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S)

i = -10**9
c = 0
cmax = 0
f = 0
while m < len(S)-N:
    k = KMP(0)
    if k == len(S):
        break
    elif k == N + i:
        c += 1
    else:
        c = 1
        f += 1
    cmax = max(cmax, c)
    i = k
if f == 1:
    print(-1)
else:
    print(cmax//p)

Submission status: Time Limit Exceeded

Solution code:
S = input()
W = input()
S *= 3 * (len(W)//len(S)+1)


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
p = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        p = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    # print("i =", i)
    k = KMP(i)
    if k + i == len(S):
        break
    elif k == len(W) - 1:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + 1
if cmax * len(W) * 3 >= len(S) * 2:
    print(-1)
else:
    print(cmax//p)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  n=len(pt)
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited,check_visited,d):
  if visited[v]==True:
    return -1,visited
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return max(d),visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited,[False]*ls,[-1]*ls)
    if tmp>ans:
      ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return max(d),visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  n=len(pt)
  d=[-1]*n
  if visited[v]==True:
    return -1,visited
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return max(d),visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  n=len(pt)
  d=[-1]*n
  if visited[v]==True:
    return -1,visited
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return max(d),visited+check_visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
W = input()
S *= 6 * (len(W)//len(S)+1)


N = len(W)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

D = divisors(N)
p = 1
for d in D:
    if W[:-d] == W[d:]:
        W = W[:d]
        p = N//d
        N = d
        break

W = W[:d]


T = [-1] * (len(W)+1)

ii = 2
jj = 0

T[0] = -1
T[1] = 0

while ii < len(W):
    if W[ii - 1] == W[jj]:
        T[ii] = jj + 1
        ii += 1
        jj += 1
    elif jj > 0:
        jj = T[jj]
    else:
        T[ii] = 0
        ii += 1

def KMP(i0):
    ret = -1
    
    m = 0
    i = 0

    while m + i < len(S) - i0:
        if W[i] == S[m + i + i0]:
            i += 1
            if i == len(W):
                return m
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return len(S) - i0

i = 0
c = 0
cmax = 0
while i < len(S):
    # print("i =", i)
    k = KMP(i)
    if k + i == len(S):
        break
    elif k == len(W) - 1:
        c += 1
    else:
        c = 1
    cmax = max(cmax, c)
    i += k + 1
if cmax * len(W) * 5 > len(S) * 4:
    print(-1)
else:
    print(cmax//p)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v):
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return d

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

ans = 0
for v in range(ls):
  if B[v]:
    tmp = max(dfs(pt,v))
    if tmp>ans:
      ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v):
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return d

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

ans = 0
for v in range(ls):
  tmp = max(dfs(pt,v))
  if tmp>ans:
    ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo_II(S,T,n):
  A=[0]*n
  counter=0
  for j1 in range(len(T)):
    if S[j1] ==T[j1]:counter+=1
    else: break
  A[0]=counter 
  i=1
  j=0
  while i<n:
    while i+j<len(S) and j<len(T):
      if S[i+j]==T[j]: j+=1
      else: break
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j=0
  B = [False]*n
  for i in range(n):
    if A[i]==len(T): B[i]=True
  return B

def dfs(pt,v):
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return d

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = s*(len(t)//ls +2)
B = Z_algo_II(s2,t,ls)

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

ans = 0
for v in range(ls):
  tmp = max(dfs(pt,v))
  if tmp>ans:
    ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def rolling_hash(s, w, MOD):
    ret = []
    tmp = 0
    p = pow(26, w, MOD)
    ords = [ord(c) - 97 for c in s]
    for i, o in enumerate(ords):
        tmp = tmp * 26 + o
        if i >= w:
            tmp = (tmp - ords[i - w] * p)
        tmp %= MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    k = (lt - 1) // ls + 1
    s *= k * 2
    ls *= k
    rs, rt = rolling_hash(s, lt, MOD), rolling_hash(t, lt, MOD)
    rs = rs[ls:]
    ht = rt[-1]

    checked = [-1] * ls

    def series(i, st):
        if i == st:
            return float('-inf')
        if checked[i] == -1:
            checked[i] = series((i + lt) % ls, st) + 1 if rs[i] == ht else 0
        return checked[i]

    for i, hs in enumerate(rs):
        if hs != ht:
            continue
        ret = series((i + lt) % ls, i)
        if ret == float('-inf'):
            return -1
        checked[i] = ret + 1

    return max(0, max(checked))


s = input()
t = input()
print(solve(s, t))

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 pi(s):
    p = [0] * len(s)
    g = 0
    for i in range(1, len(s)):
        while g and (s[i] != s[g]):
            g = p[g - 1]
        if s[i] == s[g]:
            g += 1
        p[i] = g
 
    return p
 
def match(s, pat):
    if not pat: return list(range(len(s)))
    ret = []
    p = pi(pat)
    g = 0
    for i in range(len(s)):
        while g and s[i] != pat[g]:
            g = p[g - 1]
        if s[i] == pat[g]:
            g += 1 
            if g == len(pat): 
                ret.append(i + 1 - g)
                g = p[g - 1]
    return ret
 
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 not match(s, u):
            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:
s = input()
t = input()

u = ""
while len(u) < len(s) + len(t):
    u = s * (len(t) // len(s) + 1)

t_add = t + "."


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_tx = partial_match_table(t_add)

match = [0] * len(s)

i = j = 0
while i < len(u) and j < len(t_add):
    if u[i] == t_add[j]:
        i += 1
        j += 1
    elif j == 0:
        i += 1
    else:
        j = table_tx[j]
    if j == len(t_add) - 1:
        match[(i - j) % len(s)] = 1


# search
searched = [0] * len(s)
longest = 0
infinity = False
for i in range(len(s)):
    if searched[i]:
        continue
    searched[i] = 1
    p = i
    right = 0
    while match[p]:
        right += 1
        p = (p + len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    left = 0
    p = i
    while match[(p - len(t)) % len(s)]:
        left += 1
        p = (p - len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    if left + right > longest:
        longest = left + right

if infinity:
    print(-1)
else:
    print(longest)

Submission status: Time Limit Exceeded

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

u = ""
while len(u) < len(s) + len(t):
    u = u + s

t_add = t + "."


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_tx = partial_match_table(t_add)

match = [0] * len(s)

i = j = 0
while i < len(u) and j < len(t_add):
    if u[i] == t_add[j]:
        i += 1
        j += 1
    elif j == 0:
        i += 1
    else:
        j = table_tx[j]
    if j == len(t_add) - 1:
        match[(i - j) % len(s)] = 1


# search
searched = [0] * len(s)
longest = 0
infinity = False
for i in range(len(s)):
    if searched[i]:
        continue
    searched[i] = 1
    p = i
    right = 0
    while match[p]:
        right += 1
        p = (p + len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    left = 0
    p = i
    while match[(p - len(t)) % len(s)]:
        left += 1
        p = (p - len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    if left + right > longest:
        longest = left + right

if infinity:
    print(-1)
else:
    print(longest)

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
 
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:
        if len(t)*(lo - 1) >= 2 * n:
            print(-1)
            return
        mi = (lo + hi) // 2
        if s.find(mi * t)+1:
            lo = mi + 1
        else:
            hi = mi
    if len(t)*(lo - 1) >= 2 * n:
        print(-1)
        return
    print(lo - 1)
 
 
if __name__ == "__main__":
    main()

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:
        if len(t)*(lo - 1) >= 2 * n:
            print(-1)
            return
        mi = (lo + hi) // 2
        if (mi * t) in s:
            lo = mi + 1
        else:
            hi = mi
    if len(t)*(lo - 1) >= 2 * n:
        print(-1)
        return
    print(lo - 1)
 
 
if __name__ == "__main__":
    main()