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 math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60

class RRH():
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        import random
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RRH.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [293, 389, 167]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (-(-lt // ls) * 2 + 1)
    srh = RRH(SS)
    th = RRH(T).calc(0, len(T))

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



def main():
    S = input()
    T = input()
    print(slv(S, T))



if __name__ == '__main__':
    main()

Solution (Python):

import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60


def gen(a, b, num):
    import random
    result = set()
    while 1:
        while 1:
            v = random.randint(a, b)//2*2+1
            if v not in result:
                break
        for x in range(3, int(math.sqrt(v))+1, 2):
            if v % x == 0:
                break
        else:
            result.add(v)
            if len(result) == num:
                break
    return result


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            num = ord(s[i])
            tmp = (tmp*base + num) % mod
            h[i+1] = tmp

        self.pw = pw = [1]*(len(s)+1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


class RRH():
    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = gen(2, 10**3, num)
        else:
            bases = {293, 389, 167}

        MOD = 10**9+7
        self.rhs = [RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (-(-lt // ls) * 2 + 1)
    srh = RRH(SS)
    th = RRH(T).calc(0, len(T))

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



def main():
    S = input()
    T = input()
    print(slv(S, T))



if __name__ == '__main__':
    main()

Solution (Python):
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1500000//tl + 1
r2 = r
s *= 1499999//sl + 1
n = len(s)

base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if l*tl >= 1000000:
    print(-1)
else:
    print(l)

Solution (Python):
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

import sys
from fractions import gcd

sys.setrecursionlimit(1500000)

s=input()
t=input()
n=len(s)
m=len(t)
if n!=m:
    s=(m//n+2)*s
    data=Z_algorithm(t+'?'+s)
    bool=[False for i in range(0,n)]
    for i in range(m+1,m+1+n):
        if data[i]==m:
            bool[i-m-1]=True

    g=gcd(n,m)
    for i in range(0,g):
        for j in range(0,n//g):
            if not bool[i+j*g]:
                break
        else:
            print(-1)
            exit()

    ans=[[] for i in range(0,g)]
    for i in range(0,g):
        ans[i].append(bool[i])
        x=(i+m)%n
        while x!=i:
            ans[i].append(bool[x])
            x=(x+m)%n

    from itertools import groupby
    answer=0
    for i in range(0,g):
        a=groupby(ans[i])
        d=[]
        for key,group in a:
            g=len(list(group))
            d.append([key,g])
        if d:
            if d[0][0] and d[-1][0]:
                d[-1][1]+=d[0][1]
        for j in range(len(d)):
            if d[j][0]:
                answer=max(answer,d[j][1])
    print(answer)


else:
    s=2*s
    data=Z_algorithm(t+'?'+s)
    for i in range(m+1,n+m+1):
        if data[i]==m:
            print(-1)
            break
    else:
        print(0)

Solution (Python):
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

import sys
from fractions import gcd

sys.setrecursionlimit(1500000)

s=input()
t=input()
n=len(s)
m=len(t)
if n!=m:
    s=(m//n+2)*s
    data=Z_algorithm(t+'?'+s)
    bool=[False for i in range(0,n)]
    for i in range(m+1,m+1+n):
        if data[i]==m:
            bool[i-m-1]=True

    g=gcd(n,m)
    for i in range(0,g):
        for j in range(0,n//g):
            if not bool[i+j*g]:
                break
        else:
            print(-1)
            exit()

    ans=[[] for i in range(0,g)]
    for i in range(0,g):
        ans[i].append(bool[i])
        x=(i+m)%n
        while x!=i:
            ans[i].append(bool[x])
            x=(x+m)%n

    from itertools import groupby
    answer=0
    for i in range(0,g):
        a=groupby(ans[i])
        d=[]
        for key,group in a:
            g=len(list(group))
            d.append([key,g])
        if d:
            if d[0][0] and d[-1][0]:
                d[-1][1]+=d[0][1]
        for j in range(len(d)):
            if d[j][0]:
                answer=max(answer,d[j][1])
    print(answer)


else:
    s=2*s
    data=Z_algorithm(t+'?'+s)
    for i in range(m+1,n+m+1):
        if data[i]==m:
            print(-1)
            break
    else:
        print(0)

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

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        
        if j == 0:
            i += 1
            continue

        
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 1)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
ans = 0
for i in range(n):
    c = 0
    for v in z[n + i::n]:
        if v >= n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)

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

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        
        if j == 0:
            i += 1
            continue

        
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 1)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)

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

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        
        if j == 0:
            i += 1
            continue

        
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 2)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    S = input().rstrip('\n')
    T = input().rstrip('\n')

    ns = len(S)
    nt = len(T)

    mod1 = 1000000007
    mod2 = 1000000009
    mod3 = 998244353
    b1 = 1007
    b2 = 2009
    b3 = 2999
    H1 = 0
    H2 = 0
    H3 = 0
    for i, t in enumerate(T):
        t = ord(t)
        H1 = ((H1 * b1)%mod1 + t)%mod1
        H2 = ((H2 * b2)%mod2 + t)%mod2
        H3 = ((H3 * b3)%mod3 + t)%mod3
    h1 = 0
    h2 = 0
    h3 = 0
    for i in range(nt):
        s = ord(S[i%ns])
        h1 = ((h1 * b1) % mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 + s) % mod3

    idx = []
    if h1 == H1 and h2 == H2 and h3 == H3:
        idx.append(0)
    b1_nt = pow(b1, nt, mod1)
    b2_nt = pow(b2, nt, mod2)
    b3_nt = pow(b3, nt, mod3)
    for i in range(1, ns):
        s = ord(S[(i+nt-1)%ns])
        s_prev = ord(S[i-1])
        h1 = ((h1 * b1) % mod1 - (b1_nt * s_prev)%mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 - (b2_nt * s_prev)%mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 - (b3_nt * s_prev) % mod3 + s) % mod3
        if h1 == H1 and h2 == H2 and h3 == H3:
            idx.append(i%ns)
    if len(idx) == 0:
        print(0)
        exit()
    ans = 1
    dic = {}
    for i in range(len(idx)):
        if (idx[i] - nt)%ns in dic:
            tmp = dic[(idx[i]-nt)%ns] + 1
            dic[idx[i]] = tmp
            ans = max(ans, tmp)
        else:
            dic[idx[i]] = 1
    for i in range(len(idx)):
        if (idx[i] - nt)%ns in dic:
            tmp = dic[(idx[i]-nt)%ns] + 1
            dic[idx[i]] = tmp
            ans = max(ans, tmp)
        else:
            dic[idx[i]] = 1
    ans_ = ans
    for i in range(len(idx)):
        if (idx[i] - nt)%ns in dic:
            tmp = dic[(idx[i]-nt)%ns] + 1
            dic[idx[i]] = tmp
            ans = max(ans, tmp)
        else:
            dic[idx[i]] = 1
    if ans == ans_:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
class KMP:
    def partial(self, P):
        ret = [0]
        for i in range(1, len(P)):
            j = ret[i - 1]
            while j > 0 and P[j] != P[i]:
                j = ret[j - 1]
            ret.append(j + 1 if P[j] == P[i] else j)
        return ret

    def search(self, S, P):
        partial, ret, j = self.partial(P), [], 0        
        for i in range(len(S)):
            while j > 0 and S[i] != P[j]:
                j = partial[j - 1]
            if S[i] == P[j]: j += 1
            if j == len(P): 
                ret.append(i - (j - 1))
                j = partial[j - 1]
        return ret

def main():
    S=list(map(ord,input()))
    T=list(map(ord,input()))
    N,M=len(S),len(T)
    I=KMP().search(S*(M//N+2),T)
    A=[False]*N
    B=[False]*N
    C=[0]*N
    for i in I:
        A[i%N]=True
    for i in range(N):
        if B[i]: continue
        B[i]=True
        j=i
        acc=0
        while A[j]:
            j=(j+M)%N
            acc+=1
            if B[j] and A[j]:
                C[i]=C[j]+acc
                break
            C[j]=max(C[j],acc)
            B[j]=True
        if acc and i==j:
            print(-1)
            return
        C[i]=max(C[i],acc)
    print(max(C))

if __name__ == "__main__":
    main()

Solution (Python):
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        l = len(s)
        self.pw = pw = [1]*(l+1)
        self.h = h = [0]*(l+1)
        for i in range(l):
            h[i+1] = (h[i] * base + ord(s[i])) % mod
            pw[i+1] = pw[i] * base % mod

    def get(self, l, r): 
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

def main():
  s = input()
  t = input()
  ls,lt = len(s), len(t)
  m = (ls+lt-1)//ls + 1
  s *= m
  s1 = RollingHash(s, 1007, 10**9+7)
  t1 = RollingHash(t, 1007, 10**9+7)
  w = t1.get(0,lt)
  g = [None]*ls
  for i in range(ls):
    if s1.get(i, i+lt) == w:
      g[i] = (i+lt)%ls
  
  f = [None]*ls
  for i in range(ls):
    if f[i] is None:
      f[i] = ls
      q = [i]
      while q:
        if g[q[-1]] is None:
          f[q[-1]] = 0
          q.pop()
        elif f[g[q[-1]]] is None:
          q.append(g[q[-1]])
        else:
          f[q[-1]] = f[g[q[-1]]] + 1
          q.pop()
  print(max(f) if max(f) < ls else -1)
  return
  
main()

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

def Z_algorithm(s):
	l = len(s)
	res = [-1 for _ in range(l)]
	res[0] = l
	i, j = 1, 0
	while i < l:
		while i+j < l and s[j] == s[i+j]:
			j += 1
		res[i] = j

		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while i+k < l and k + res[k] < j:
				res[i+k] = res[k]
				k += 1

			i += k
			j -= k

	return res

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
ts_concat = t + " " + s_concat
z = Z_algorithm(ts_concat)

adj = [-1 for _ in range(ns)]

for i in range(1, len(z)):
	if i-nt-1 >= ns:
		break
	if z[i] == nt:
		j = i-nt-1
		if j == (j+nt)%ns:
			print(-1)
			sys.exit()
		adj[j] = (j+nt)%ns

visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

def Z_algorithm(s):
	l = len(s)
	res = [-1 for _ in range(l)]
	res[0] = l
	i, j = 1, 0
	while i < l:
		while i+j < l and s[j] == s[i+j]:
			j += 1
		res[i] = j

		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while i+k < l and k + res[k] < j:
				res[i+k] = res[k]
				k += 1

			i += k
			j -= k

	return res

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
ts_concat = t + " " + s_concat
z = Z_algorithm(ts_concat)

adj = [-1 for _ in range(ns)]

for i in range(1, len(z)):
	if i-nt-1 >= ns:
		break
	if z[i] == nt:
		j = i-nt-1
		if j == (j+nt)%ns:
			print(-1)
			sys.exit()
		adj[j] = (j+nt)%ns

visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

class KMP():
	def __init__(self, sentence):
		self.sentence = sent = sentence
		self.l = l = len(sent)
		self.table = table = [0 for _ in range(l+1)]
		table[0] = -1
		j = -1
		for i in range(l):
			while j >= 0 and sent[i] != sent[j]:
				j = table[j]
			j += 1
			if i < l-1 and sent[i+1] == sent[j]:
				table[i+1] = table[j]
			else:
				table[i+1] = j

	def search(self, key):
		table = self.table
		sent = self.sentence
		l = self.l
		i = 0
		res = []
		for j in range(len(key)):
			while i > -1 and sent[i] != key[j]:
				i = table[i]
			i += 1
			if i >= l:
				res.append(j-i+1)
				i = table[i]
		return res


s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s

adj = [-1 for _ in range(ns)]

kmp = KMP(t)
matches = kmp.search(s_concat)

for i in matches:
	if i >= ns:
		break
	if i == (i+nt)%ns:
		print(-1)
		sys.exit()
	adj[i] = (i+nt)%ns


visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

class KMP():
	def __init__(self, sentence):
		self.sentence = sent = sentence
		self.l = l = len(sent)
		self.table = table = [0 for _ in range(l+1)]
		table[0] = -1
		j = -1
		for i in range(l):
			while j >= 0 and sent[i] != sent[j]:
				j = table[j]
			j += 1
			if i < l-1 and sent[i+1] == sent[j]:
				table[i+1] = table[j]
			else:
				table[i+1] = j

	def search(self, key):
		table = self.table
		sent = self.sentence
		l = self.l
		i = 0
		res = []
		for j in range(len(key)):
			while i > -1 and sent[i] != key[j]:
				i = table[i]
			i += 1
			if i >= l:
				res.append(j-i+1)
				i = table[i]
		return res


s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s

adj = [-1 for _ in range(ns)]

kmp = KMP(t)
matches = kmp.search(s_concat)

for i in matches:
	if i >= ns:
		break
	if i == (i+nt)%ns:
		print(-1)
		sys.exit()
	adj[i] = (i+nt)%ns


visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Solution (Python):
import os
import sys

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

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





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

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

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


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


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




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

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

Solution (Python):

import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [-1 for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i] = (i+nt)%ns

visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Solution (Python):
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

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0
    results = []
    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
            if p == len(word):
                p = table[p]
                results.append((i-len(word), i))
        elif p == 0:
            i += 1
        else:
            p = table[p]
    return results

inf = 10**18
s = input().strip()
t = input().strip()
m=(len(t)+len(s)-1+len(s)-1)//len(s)
d = set()
for a, b in kmp_search(m*s, t):
    d.add(a%len(s))

d2 = set()
for i in range(len(s)):
    if i not in d:
        d2.add(i)
q = d2

LT, LS = len(t), len(s)
dist = [inf] * LS
d = 0
while q:
    qq = []
    for x in q:
        if dist[x] == inf:
            dist[x] = d
            qq.append((x-LT)%LS)
    d += 1
    q = qq

answer = max(dist)
if answer >= inf:
    answer = -1

print(answer)