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.

Solution (Python):

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
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        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)

Solution (Python):
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 st <= i < st + lt:
            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))

Solution (Python):

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]
        p[i] = g = g + (s[i] == s[g])

    return p


def match(s, pat, uniq='\0'):
    return [i + 1 - c for i, c in enumerate(pi(pat + uniq + s)[len(pat) + 1:]) if c == len(pat)]
 
 
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)
 
 

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

 
if __name__ == "__main__":
    main()

Solution (Python):

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 partial(S):
    P = [0] * len(S)
    g = 0
    for i in range(1, len(S)):
        while g and (S[g] != S[i]):
            g = P[g - 1]
        P[i] = g = g + (S[g] == S[i])
 
    return P
 
def match(S, pattern):
    if not pattern: return list(range(len(S)))
    P = partial(pattern)
    g = 0
    ret = []
    
    for i in range(len(S)):
        while g and pattern[g] != S[i]:
            g = P[g - 1]
        g += pattern[g] == S[i]
        if g == len(P): 
            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)
 
 

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

 
if __name__ == "__main__":
    main()

Solution (Python):

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]
        g += s[i] == s[g]
        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]
        g += s[i] == pat[g]
        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)
 
 

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

 
if __name__ == "__main__":
    main()

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

u = s * (len(t) // len(s) + 2)

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



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)

Solution (Python):

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)
    for i in range(1, len(s)):
        g = p[i - 1]
        while g and (s[i] != s[g]):
            g = p[g - 1]
        p[i] = g + int(s[i] == s[g])

    return p


def match(s, pat):
    res = []
    p = pi(pat + '\0' + s)
    for i in range(len(p) - len(s), len(p)):
        if p[i] == len(pat):
            res.append(i - 2 * len(pat))

    return res


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

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

    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)




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



if __name__ == "__main__":
    main()

Solution (Python):

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)
    for i in range(1, len(s)):
        g = p[i - 1]
        while g and (s[i] != s[g]):
            g = p[g - 1]
        p[i] = g + int(s[i] == s[g])

    return p


def match(s, pat):
    res = []
    p = pi(pat + '\0' + s)
    for i in range(len(p) - len(s), len(p)):
        if p[i] == len(pat):
            res.append(i - 2 * len(pat))

    return res


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)




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



if __name__ == "__main__":
    main()

Solution (Python):
import sys

stdin = sys.stdin

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

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

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

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) <= 4*len(t):
    m = m + m
while len(t) < len(m):
    t = t + t

zx = z(t+"$"+m)

ans = max(zx[len(t)+1:])
print(ans//lt)

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

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

S,T


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)