AtCoder Beginner Contest 135 - Strings of Eternity

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-----
abcabab
ab

-----Sample Output-----
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.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
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()


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)
main()


S = list(input())
T = list(input())
len0 = len(S)
S = S * (len(T) // len0 + 1)
S = S + S
p = 26
mod = (1 << 31) + 7
TABLE = [0]
LEN = len(S)
for i in range(LEN):
	TABLE.append((p * TABLE[-1] % mod + ord(S[i]) - 97) % mod)
NOW = 0
LEN2 = len(T)
for i in range(LEN2):
	NOW = (p * NOW % mod + ord(T[i]) - 97) % mod
TH = NOW

def hash_ij(i, j):
	return (TABLE[j] - TABLE[i] * pow(p, j - i, mod)) % mod
OK = [0] * LEN
for i in range(LEN2, LEN):
	if hash_ij(i - LEN2, i) == TH:
		OK[i - LEN2] = 1
OK = OK[:len0]
ANS = 0
ST = [-1] * len0
for i in range(len0):
	if OK[i] == 1 and ST[i] == -1:
		j = i
		count = 0
		while OK[j] == 1:
			if ST[j] != -1:
				count += ST[j]
				break
			count += 1
			ST[j] = 1
			j = (j + LEN2) % len0
			if j == i:
				print(-1)
				import sys
				sys.exit()
		ST[i] = count
		ANS = max(ANS, count)
print(ANS)


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)


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

	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)
		(i, p) = (0, 0)
		match = []
		while i < len(S) and p < len(word):
			if S[i] == word[p]:
				i += 1
				p += 1
				if p == len(word):
					match.append(i - p)
					p = table[p]
			elif 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):
			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) = (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):
			return self.find(x) == self.find(y)

		def size(self, 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):
			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
	N = len(S)
	n = len(T)
	V = [[] for _ in range(N)]
	S *= 2
	kmp = KMP(S, T)
	for i in kmp:
		if i >= N:
			continue
		V[i % N].append((i + n) % N)
	uf = UnionFind(N)

	def dfs(s):
		cnt = 0
		for v in V[s]:
			if uf.same(s, v):
				return -1
			if uf.size(v) > 1:
				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)
		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)
examF()


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

def Z_find(txt, pattern):
	lp = len(pattern)
	jointxt = pattern + '-' + txt
	Z = Z_algorithm(jointxt)
	return [Z[i] == lp for i in range(lp + 1, len(jointxt))]

def solve(s, t):
	ls = len(s)
	lt = len(t)
	Judge = Z_find(s * 2, t)
	ret = 0
	Visited = [-1] * ls
	for i in range(ls):
		if Judge[i] and Visited[i] == -1:
			idx = i
			cnt = 0
			while Judge[idx]:
				if Visited[idx] != -1:
					cnt += Visited[idx]
					break
				cnt += 1
				Visited[idx] = 1
				idx = (idx + lt) % ls
				if idx == i:
					return -1
			Visited[i] = cnt
			ret = max(ret, cnt)
	return ret
s = input()
t = input()
s *= (len(t) + len(s) - 1) // len(s)
print(solve(s, t))


def getTableKMP(Ss):
	Ss += '$'
	lenS = len(Ss)
	table = [-1] * lenS
	j = -1
	for i in range(lenS - 1):
		while j >= 0 and Ss[i] != Ss[j]:
			j = table[j]
		j += 1
		if Ss[i + 1] == Ss[j]:
			table[i + 1] = table[j]
		else:
			table[i + 1] = j
	return table

def getPosPtnsKMP(Ss, ptn, table):
	anss = []
	(lenS, lenP) = (len(Ss), len(ptn))
	(iS, iP) = (0, 0)
	while iS < lenS:
		if Ss[iS] == ptn[iP]:
			iS += 1
			iP += 1
			if iP == lenP:
				anss.append(iS - lenP)
				iP = table[iP]
		else:
			iP = table[iP]
			if iP == -1:
				iS += 1
				iP = 0
	return anss
Ss = input()
Ts = input()
(lenS, lenT) = (len(Ss), len(Ts))
num = (lenT + lenS - 1 + lenS - 1) // lenS
S2s = Ss * num
tableKMP = getTableKMP(Ts)
posPtns = getPosPtnsKMP(S2s, Ts, tableKMP)
isFounds = [False] * lenS
for pos in posPtns:
	if pos >= lenS:
		break
	isFounds[pos] = True
ans = 0
numDone = 0
for i in range(lenS):
	if not isFounds[i]:
		i = (i + lenT) % lenS
		for num in range(lenS + 1):
			if not isFounds[i]:
				ans = max(ans, num)
				numDone += num + 1
				break
			i = (i + lenT) % lenS
		else:
			ans = -1
			break
if numDone < lenS:
	ans = -1
print(ans)


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)


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))
main()


s = input()
t = input()

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

def solve(i, li):
	ans = 0
	while True:
		if i < 0 or len(li) <= i or visited[i]:
			break
		if li[i] < len(t):
			visited[i] = True
			break
		if li[i] >= len(t):
			visited[i] = True
			ans += 1
			i += len(t)
	return ans
new_s = s
while True:
	if len(new_s) > len(t):
		s = new_s
		break
	new_s += new_s
s = s * 3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
	ans1 = max(ans1, solve(i, li))
s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
	ans2 = max(ans2, solve(i, li))
if ans1 == ans2:
	print(ans1)
else:
	print(-1)


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)


import collections

class KMP:

	def __init__(self, pattern):
		self.pattern = pattern
		self.n = len(pattern)
		self.create_k_table()

	def create_k_table(self):
		ktable = [-1] * (self.n + 1)
		j = -1
		for i in range(self.n):
			while j >= 0 and self.pattern[i] != self.pattern[j]:
				j = ktable[j]
			j += 1
			if i + 1 < self.n and self.pattern[i + 1] == self.pattern[j]:
				ktable[i + 1] = ktable[j]
			else:
				ktable[i + 1] = j
		self.ktable = ktable

	def match(self, s):
		n = len(s)
		j = 0
		ret = [0] * n
		for i in range(n):
			while j >= 0 and (j == self.n or s[i] != self.pattern[j]):
				j = self.ktable[j]
			j += 1
			if j == self.n:
				ret[(i - self.n + 1) % n] = 1
		return ret

def main():
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	k = 1 - -(m - 1) // n
	si = s * k
	a = KMP(t)
	b = a.match(si)
	edges = [[] for i in range(n)]
	indegree = [0] * n
	for i in range(n):
		k = (i + m) % n
		if b[i]:
			edges[i].append(k)
			indegree[k] += 1

	def topSort():
		q = collections.deque([i for i in range(n) if indegree[i] == 0])
		while q:
			cur = q.popleft()
			res.append(cur)
			for nei in edges[cur]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					q.append(nei)
		return len(res) == n
	res = []
	dp = [0] * n
	flag = topSort()
	if flag:
		for k in range(n):
			i = res[k]
			for j in edges[i]:
				dp[j] = max(dp[j], dp[i] + 1)
		ans = max(dp)
	else:
		ans = -1
	return ans
print(main())


S = input()
T = input()
len0 = len(S)
S = S * ((len(T) + len(S) - 1) // len(S) * 2)
MOD = 2 ** 31 + 7
base = 26
hashS = [0]
hashT = 0
for s in S:
	hashS.append((hashS[-1] * base + ord(s) - 97) % MOD)
for t in T:
	hashT = (hashT * base + ord(t) - 97) % MOD
ok = [False] * len0
for i in range(len0):
	if (hashS[i + len(T)] - hashS[i] * pow(base, len(T), MOD)) % MOD == hashT:
		ok[i] = True

def solve():
	ret = 0
	visited = [-1] * len0
	for i in range(len0):
		if ok[i] and visited[i] == -1:
			j = i
			count = 0
			while ok[j]:
				if visited[j] != -1:
					count += visited[j]
					break
				count += 1
				visited[j] = 1
				j = (j + len(T)) % len0
				if j == i:
					return -1
			visited[i] = count
			ret = max(ret, count)
	return ret
print(solve())


def z_algorithm(s):
	n = len(s)
	z = [0] * n
	z[0] = n
	i = 1
	lcp = 0
	while i < n:
		while i + lcp < n and s[i + lcp] == s[lcp]:
			lcp += 1
		z[i] = lcp
		if lcp == 0:
			i += 1
			continue
		k = 1
		while i + k < n and k + z[k] < lcp:
			z[i + k] = z[k]
			k += 1
		i += k
		lcp -= k
	return z
from collections import deque

def topological_sort(graph: list, n_v: int) -> list:
	indegree = [0] * n_v
	for i in range(n_v):
		for v in graph[i]:
			indegree[v] += 1
	cand = deque([i for i in range(n_v) if indegree[i] == 0])
	res = []
	while cand:
		v1 = cand.popleft()
		res.append(v1)
		for v2 in graph[v1]:
			indegree[v2] -= 1
			if indegree[v2] == 0:
				cand.append(v2)
	return res
import sys

def main():
	input = sys.stdin.readline
	s = input().rstrip()
	t = input().rstrip()
	n0 = len(s)
	m = len(t)
	s = s * (m // n0 + 2)
	z = z_algorithm(t + '*' + s)
	z = z[m + 1:]
	graph = [[] for _ in range(n0)]
	for i in range(n0):
		if z[i] >= m:
			graph[i].append((i + m) % n0)
	ts = topological_sort(graph, n0)
	if len(ts) != n0:
		ans = -1
	else:
		ans = 0
		path = [0] * n0
		for i in range(n0):
			ans = max(ans, path[ts[i]])
			for j in graph[ts[i]]:
				path[j] = path[ts[i]] + 1
	print(ans)
main()


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)


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)


from collections import defaultdict
mod1 = 10 ** 9 + 7
base1 = 1007

def getlist():
	return list(map(int, input().split()))

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)
		self.judge = 'No'

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			if self.same_check(x, y) != True:
				self.size[y] += self.size[x]
				self.size[x] = 0
			else:
				self.judge = 'Yes'
			self.par[x] = y
		else:
			if self.same_check(x, y) != True:
				self.size[x] += self.size[y]
				self.size[y] = 0
			else:
				self.judge = 'Yes'
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def siz(self, x):
		x = self.find(x)
		return self.size[x]

def rollingHash(N, M, A):
	mul1 = 1
	for i in range(M):
		mul1 = mul1 * base1 % mod1
	val1 = 0
	for i in range(M):
		val1 = val1 * base1 + A[i]
		val1 %= mod1
	hashList1 = [None] * (N - M + 1)
	hashList1[0] = val1
	for i in range(N - M):
		val1 = (val1 * base1 - A[i] * mul1 + A[i + M]) % mod1
		hashList1[i + 1] = val1
	return hashList1

def main():
	s = list(input())
	t = list(input())
	N = len(s)
	M = len(t)
	if N < M:
		var = int(M // N) + 1
		s = s * var
		N = N * var
	s = s + s
	for i in range(2 * N):
		s[i] = ord(s[i]) - 97
	for i in range(M):
		t[i] = ord(t[i]) - 97
	sHash1 = rollingHash(2 * N, M, s)
	tHash1 = rollingHash(M, M, t)
	tHash1 = tHash1[0]
	value = 'No'
	UF = UnionFind(N)
	for i in range(N):
		j = (i + M) % N
		if sHash1[i] == tHash1:
			value = 'Yes'
			if sHash1[j] == tHash1:
				UF.union(i, j)
	if value == 'No':
		print(0)
		return
	if UF.judge == 'Yes':
		print(-1)
		return
	for i in range(N):
		UF.par[i] = UF.find(i)
	ans = 0
	for i in range(N):
		ans = max(ans, UF.size[i])
	print(ans)
main()


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)


class RollingHash:

	def __init__(self, s):
		self.length = len(s)
		self.base1 = 1009
		self.base2 = 1013
		self.mod1 = 10 ** 9 + 7
		self.mod2 = 10 ** 9 + 9
		self.hash1 = [0] * (self.length + 1)
		self.hash2 = [0] * (self.length + 1)
		self.pow1 = [1] * (self.length + 1)
		self.pow2 = [1] * (self.length + 1)
		for i in range(self.length):
			self.hash1[i + 1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
			self.hash2[i + 1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
			self.pow1[i + 1] = self.pow1[i] * self.base1 % self.mod1
			self.pow2[i + 1] = self.pow2[i] * self.base2 % self.mod2

	def get(self, l, r):
		h1 = ((self.hash1[r] - self.hash1[l] * self.pow1[r - l]) % self.mod1 + self.mod1) % self.mod1
		h2 = ((self.hash2[r] - self.hash2[l] * self.pow2[r - l]) % self.mod2 + self.mod2) % self.mod2
		return (h1, h2)

def solve(s, t):
	ls = len(s)
	lt = len(t)
	RHs = RollingHash(s * 2)
	RHt = RollingHash(t)
	Judge = [False] * ls
	B = RHt.get(0, lt)
	for i in range(ls):
		if RHs.get(i, i + lt) == B:
			Judge[i] = True
	ret = 0
	Visited = [-1] * ls
	for i in range(ls):
		if Judge[i] and Visited[i] == -1:
			idx = i
			cnt = 0
			while Judge[idx]:
				if Visited[idx] != -1:
					cnt += Visited[idx]
					break
				cnt += 1
				Visited[idx] = 1
				idx = (idx + lt) % ls
				if idx == i:
					return -1
			Visited[i] = cnt
			ret = max(ret, cnt)
	return ret
s = input()
t = input()
s *= (len(t) + len(s) - 1) // len(s)
print(solve(s, t))


class KMP:

	def __init__(self, pattern):
		self.pattern = pattern
		self.n = len(pattern)
		self.create_k_table()

	def create_k_table(self):
		ktable = [-1] * (self.n + 1)
		j = -1
		for i in range(self.n):
			while j >= 0 and self.pattern[i] != self.pattern[j]:
				j = ktable[j]
			j += 1
			if i + 1 < self.n and self.pattern[i + 1] == self.pattern[j]:
				ktable[i + 1] = ktable[j]
			else:
				ktable[i + 1] = j
		self.ktable = ktable

	def match(self, s):
		n = len(s)
		j = 0
		ret = [0] * n
		for i in range(n):
			while j >= 0 and (j == self.n or s[i] != self.pattern[j]):
				j = self.ktable[j]
			j += 1
			if j == self.n:
				ret[(i - self.n + 1) % n] = 1
		return ret

def main():
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	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)
	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)
main()


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
	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[top] = right
		left = 1
		if right == 0:
			top += 1
			continue
		while left + lcp[left] < right and left < right:
			lcp[top + left] = lcp[left]
			left += 1
		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))


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):
		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):
		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 = [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)


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 - 1]
				results.append((i - len(word), i))
				i -= 1
		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)
es = set()
d = [set() for _ in range(len(s) + 1)]
d2 = [set() for _ in range(len(s) + 1)]
for (a, b) in kmp_search(m * s, t):
	(a, b) = (a % len(s) + 1, b % len(s) + 1)
	es.add((a, b))
	d[a].add(b)
	d2[b].add(a)
fs = set()
r = 0
for x in range(len(s) + 1):
	if x in fs:
		continue
	vs = set()
	vs.add(x)
	fs.add(x)
	depths = dict()
	depths[x] = 0
	stack = [x]
	mt = x
	while stack:
		v = stack.pop()
		if v > 0:
			for u in d[v]:
				if u in vs:
					r = inf
					break
				stack.append(-v)
				stack.append(u)
				depths[u] = depths[v] + 1
				if depths[u] > depths[mt]:
					mt = u
				vs.add(u)
				fs.add(u)
		else:
			pass
	vs = set()
	vs.add(mt)
	depths = dict()
	depths[mt] = 0
	stack = [mt]
	mt2 = mt
	while stack:
		v = stack.pop()
		if v > 0:
			for u in d2[v]:
				if u in vs:
					r = inf
					break
				stack.append(-v)
				stack.append(u)
				depths[u] = depths[v] + 1
				if depths[u] > depths[mt2]:
					mt2 = u
				vs.add(u)
				fs.add(u)
		else:
			pass
	r = max(depths[mt2], r)
print(r if r != inf else -1)


import sys
input = sys.stdin.readline

class RollingHash:

	def __init__(self, s):
		self.base1 = 1009
		self.base2 = 1007
		self.mod1 = pow(10, 9) + 7
		self.mod2 = pow(10, 9) + 9
		self.hash1 = [0 for _ in range(len(s) + 1)]
		self.hash2 = [0 for _ in range(len(s) + 1)]
		self.pow1 = [1 for _ in range(len(s) + 1)]
		self.pow2 = [1 for _ in range(len(s) + 1)]
		for i in range(len(s)):
			self.hash1[i + 1] = (self.hash1[i] * self.base1 + ord(s[i])) % self.mod1
			self.hash2[i + 1] = (self.hash2[i] * self.base2 + ord(s[i])) % self.mod2
			self.pow1[i + 1] = self.pow1[i] * self.base1 % self.mod1
			self.pow2[i + 1] = self.pow2[i] * self.base2 % self.mod2

	def get(self, l, r):
		t1 = (self.hash1[r] - self.hash1[l] * self.pow1[r - l]) % self.mod1
		t2 = (self.hash2[r] - self.hash2[l] * self.pow2[r - l]) % self.mod2
		return (t1, t2)

	def add(self, t):
		offset = len(self.hash1)
		self.hash1 += [0 for _ in range(len(t))]
		self.hash2 += [0 for _ in range(len(t))]
		self.pow1 += [0 for _ in range(len(t))]
		self.pow2 += [0 for _ in range(len(t))]
		for i in range(offset, offset + len(t)):
			self.hash1[i] = (self.hash1[i - 1] * self.base1 + t[i]) % self.mod1
			self.hash2[i] = (self.hash2[i - 1] * self.base2 + t[i]) % self.mod2
			self.pow1[i] = self.pow1[i - 1] * self.base1 % self.mod1
			self.pow2[i] = self.pow2[i - 1] * self.base2 % self.mod2

class UnionFind:

	def __init__(self, size):
		self.parent = [i for i in range(size)]
		self.height = [1 for _ in range(size)]
		self.size = [1 for _ in range(size)]

	def root(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.root(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		(px, py) = (self.root(x), self.root(y))
		if px == py:
			return
		if self.height[px] <= self.height[py]:
			self.parent[px] = py
			self.size[py] += self.size[px]
			if self.height[px] == self.height[py]:
				self.height[py] += 1
		else:
			self.parent[py] = px
			self.size[px] += self.size[py]

def main():
	s = input().strip()
	t = input().strip()
	ns = len(s)
	nt = len(t)
	s = s * (len(t) // len(s) + 1) * 2
	srol = RollingHash(s)
	trol = RollingHash(t)
	uni = UnionFind(ns)
	same = [False for _ in range(ns)]
	for i in range(len(s) - len(t) + 1):
		if srol.get(i, i + nt) == trol.get(0, nt):
			same[i % ns] = True
	for i in range(ns):
		if same[i] and same[(i + nt) % ns]:
			if uni.root(i) == uni.root((i + nt) % ns):
				print(-1)
				sys.exit(0)
			else:
				uni.union(i, (i + nt) % ns)
	ans = 0
	for i in range(ns):
		if same[i]:
			ans = max(ans, uni.size[i])
	print(ans)
main()


class RollingHash:

	def __init__(self, s):
		self.length = len(s)
		self.base1 = 1009
		self.base2 = 1000
		self.mod1 = 10 ** 9 + 7
		self.mod2 = 10 ** 9 + 9
		self.hash1 = [0] * (self.length + 1)
		self.hash2 = [0] * (self.length + 1)
		self.pow1 = [1] * (self.length + 1)
		self.pow2 = [1] * (self.length + 1)
		for i in range(self.length):
			self.hash1[i + 1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
			self.hash2[i + 1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
			self.pow1[i + 1] = self.pow1[i] * self.base1 % self.mod1
			self.pow2[i + 1] = self.pow2[i] * self.base2 % self.mod2

	def get(self, l, r):
		t1 = ((self.hash1[r] - self.hash1[l] * self.pow1[r - l]) % self.mod1 + self.mod1) % self.mod1
		t2 = ((self.hash2[r] - self.hash2[l] * self.pow2[r - l]) % self.mod2 + self.mod2) % self.mod2
		return (t1, t2)
t_tmp = input().rstrip()
s = input().rstrip()
if t_tmp.count(t_tmp[0]) == len(t_tmp) and s.count(s[0]) == len(s) and (s[0] == t_tmp[0]):
	print(-1)
	exit()
t = ''
while len(t) <= len(s):
	t += t_tmp
max_ans = len(t) * 3 // len(s)
t = t * 4
lent = len(t)
lens = len(s)
RHt = RollingHash(t)
RHs = RollingHash(s)
s_hash = RHs.get(0, lens)
match = [0] * (lent - lens + 1)
for i in range(lent - lens + 1):
	if RHt.get(i, i + lens) == s_hash:
		match[i] = 1
ans = max(match[:lens])
for i in range(len(match) - lens):
	if match[i + lens] != 0:
		match[i + lens] += match[i]
		ans = max(ans, match[i + lens])
if ans > max_ans:
	print(-1)
else:
	print(ans)


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


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

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

class UnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self._size = [1] * N
		self.count = 0

	def root(self, a):
		if self.parent[a] == a:
			return a
		else:
			self.parent[a] = self.root(self.parent[a])
			return self.parent[a]

	def is_same(self, a, b):
		return self.root(a) == self.root(b)

	def unite(self, a, b):
		ra = self.root(a)
		rb = self.root(b)
		if ra == rb:
			return
		if self._size[ra] < self._size[rb]:
			(ra, rb) = (rb, ra)
		self._size[ra] += self._size[rb]
		self.parent[rb] = ra
		self.count += 1

	def size(self, a):
		return self._size[self.root(a)]

def solve():
	(ls, lt) = (len(S), len(T))
	ns = 0 - -(lt + ls) // ls
	za = z_algorithm(T + '#' + S * ns)
	from fractions import gcd
	g = gcd(ls, lt)
	uf = UnionFind(ls)
	match = False
	for i in range(ls):
		if za[lt + 1 + i] == lt:
			match = True
			j = (i + lt) % ls
			if uf.is_same(i, j):
				if uf.size(i) == ls // g:
					print(-1)
					exit()
				continue
			uf.unite(i, j)
	if not match:
		print(0)
		exit()
	ans = 0
	for i in range(ls):
		ans = max(ans, uf.size(i) - 1)
	print(ans)
solve()


from collections import defaultdict

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

class UnionFind:

	def __init__(self, num):
		self.table = [-1 for _ in range(num)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] <= self.table[s2]:
				self.table[s1] += self.table[s2]
				self.table[s2] = s1
			else:
				self.table[s2] += self.table[s1]
				self.table[s1] = s2
			return True
		return False
s = input()
t = input()
S = s * (len(t) // len(s) + 2)
z = Z(t + '*' + S)
z = z[len(t) + 1:]
u = UnionFind(len(s))
loop = False
for i in range(len(s)):
	j = (i + len(t)) % len(s)
	if z[i] == len(t) and z[j] == len(t):
		loop = not u.union(i, j) or loop
if loop:
	ans = -1
else:
	d = defaultdict(list)
	for i in range(len(s)):
		if z[i] == len(t):
			d[u.find(i)].append(i)
	ans = 0
	for k in d:
		ans = max(ans, len(d[k]))
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
s = list(input())
t = list(input())
tsr = list(t) + list(s)
while len(tsr) < 2 * len(t) + len(s):
	tsr += s

def z_alg(S):
	NN = len(S)
	Z = [NN] + [0] * (NN - 1)
	(i, j) = (1, 0)
	while i < NN:
		while i + j < NN and S[j] == S[i + j]:
			j += 1
		if not j:
			i += 1
			continue
		Z[i] = j
		k = 1
		while NN - i > k and k < j - Z[k]:
			Z[i + k] = Z[k]
			k += 1
		i += k
		j -= k
	return Z
zlist = z_alg(tsr)
match_list = []
for i in range(len(s)):
	match_list.append(zlist[i + len(t)] >= len(t))
path = [-1] * len(s)
for i in range(len(s)):
	if match_list[i]:
		path[i] = (i + len(t)) % len(s)
dist = [-1] * len(s)
for i in range(len(s)):
	if dist[i] != -1:
		continue
	d = 0
	offset = 0
	stack = [i]
	ii = i
	while path[ii] != -1:
		if d > len(s):
			print(-1)
			sys.exit(0)
		elif dist[ii] != -1:
			offset = dist[ii]
			break
		ii = path[ii]
		stack.append(ii)
		d += 1
	cnt = 0
	while stack:
		p = stack.pop()
		dist[p] = offset + cnt
		cnt += 1
print(max(dist))


import sys
sys.setrecursionlimit(10 ** 7)
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
from collections import deque, defaultdict
from collections import Counter
from itertools import accumulate, combinations, permutations, product
from heapq import heapify, heappop, heappush
from functools import reduce, lru_cache
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 = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x += x >> 8
	x += x >> 16
	x += x >> 32
	return x & 127

def main():
	mod = 1000000007

	class rh:

		def __init__(self, base=26, max_n=5 * 10 ** 5):
			self.mod = random.randrange(1 << 54 - 1, 1 << 55 - 1, 2)
			self.base = int(base * 0.5 + 0.5) * 2
			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)

		def get(self, 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):
			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))
main()


def getTableMP(Ss):
	lenS = len(Ss)
	table = [-1] * (lenS + 1)
	j = -1
	for i in range(lenS):
		while j >= 0 and Ss[i] != Ss[j]:
			j = table[j]
		j += 1
		table[i + 1] = j
	return table
Ss = input()
Ts = input()
(lenS, lenT) = (len(Ss), len(Ts))
num = (lenT + lenS - 1 + lenS - 1) // lenS
S2s = Ss * num
tableMP = getTableMP(Ts + '$' + S2s)
isFounds = [False] * lenS
for i in range(2 * lenT + 1, 2 * lenT + lenS + 1):
	if tableMP[i] >= lenT:
		isFounds[i - 2 * lenT - 1] = True
ans = 0
numDone = 0
for i in range(lenS):
	if not isFounds[i]:
		i = (i + lenT) % lenS
		for num in range(lenS + 1):
			if not isFounds[i]:
				ans = max(ans, num)
				numDone += num + 1
				break
			i = (i + lenT) % lenS
		else:
			ans = -1
			break
if numDone < lenS:
	ans = -1
print(ans)


s = input()
t = input()

def Z(S):
	A = [0] * len(S)
	i = 1
	j = 0
	A[0] = len(S)
	while i < len(S):
		while i + j < len(S) and S[j] == S[i + j]:
			j += 1
		A[i] = j
		if not j:
			i += 1
			continue
		k = 1
		while len(S) - i > k < j - A[k]:
			A[i + k] = A[k]
			k += 1
		i += k
		j -= k
	return A
z = Z(t + '?' + s * (len(t) // len(s) + 2))
z = z[len(t) + 1:]

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * n
		self.rank = [0] * n

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

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

	def card(self, x):
		return -self.root[self.find(x)]
u = UnionFind(len(s))
for i in range(len(s)):
	if z[i] == len(t):
		if u.same(i, (i + len(t)) % len(s)):
			print(-1)
			exit()
		u.unite(i, (i + len(t)) % len(s))
print(-1 + max(map(lambda x: -x, u.root)))


def f_strings_of_eternity(S, T):
	length_s = len(S)
	length_t = len(T)
	n = (length_t + -length_t % length_s) // length_s
	s = (S * (n + 1))[:length_s + length_t]
	t = T
	MOD = 10 ** 16 + 61
	base = 26
	base_inv = pow(base, MOD - 2, MOD)
	power = [1] * (length_s + length_t)
	power_inv = [1] * (length_s + length_t)
	for n in range(1, length_s + length_t):
		power[n] = power[n - 1] * base % MOD
		power_inv[n] = power_inv[n - 1] * base_inv % MOD

	def to_rolling_hash(string):
		ret = [0] * len(string)
		for (i, c) in enumerate(string):
			ret[i] = (ret[i - 1] + power[i] * ord(c)) % MOD
		return ret
	hash_s = to_rolling_hash(s) + [0]
	hash_t = to_rolling_hash(t)[-1]
	INF = float('inf')
	can_start = [(hash_s[i + length_t - 1] - hash_s[i - 1]) * power_inv[i] % MOD == hash_t for i in range(length_s)]
	num_continuation = [INF] * length_s
	queue = [(i, 0) for (i, bool) in enumerate(can_start) if not bool]
	while queue:
		q_new = []
		for (x, d) in queue:
			if num_continuation[x] == INF:
				num_continuation[x] = d
				q_new.append(((x - length_t) % length_s, d + 1))
		queue = q_new
	ans = max(num_continuation)
	return ans if ans != INF else -1
S = input()
T = input()
print(f_strings_of_eternity(S, T))


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)
main()


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


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

def Z_find(txt, pattern):
	lp = len(pattern)
	jointxt = pattern + '-' + txt
	Z = Z_algorithm(jointxt)
	return [Z[i] == lp for i in range(lp + 1, len(jointxt))]

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [0] * n
		self.size = [1] * n

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if px != py:
			if self.rank[px] == self.rank[py]:
				self.rank[px] += 1
			elif self.rank[px] < self.rank[py]:
				(px, py) = (py, px)
			self.par[py] = px
			self.size[px] += self.size[py]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

def solve(s, t):
	lt = len(t)
	s *= (lt + len(s) - 1) // len(s)
	ls = len(s)
	Z = Z_find(s * 2, t)
	uf = UnionFind(ls)
	loop = False
	for i in range(ls):
		if Z[i]:
			j = (i + lt) % ls
			if uf.same_check(i, j):
				return -1
			uf.union(i, j)
	return max(uf.size) - 1
s = input()
t = input()
print(solve(s, t))


import sys
import math
from collections import defaultdict
sys.setrecursionlimit(10 * 6)
INF = float('inf')

def z_algorithm(S):
	N = len(S)
	Z = [0] * N
	c = 0
	for i in range(1, N):
		if i + Z[i - c] < c + Z[c]:
			Z[i] = Z[i - c]
		else:
			j = max(0, c + Z[c] - i)
			while i + j < N and S[j] == S[i + j]:
				j += 1
			Z[i] = j
			c = i
	Z[0] = len(S)
	return Z

def zfindall(text, pattern, separator='$'):
	N = len(pattern)
	conc = pattern + separator + text
	Z = z_algorithm(conc)
	return [i - N - 1 for i in range(len(conc)) if Z[i] == N]

def solve(s: str, t: str):
	S = len(s)
	T = len(t)
	if T > S:
		s *= int(math.ceil(T / S))
	s2 = s + s
	match = zfindall(s2, t)
	if len(match) == 0:
		print(0)
		return
	edges = {}
	rev_edges = {}
	for (i, m) in enumerate(match):
		if m >= S:
			continue
		edges[m] = (m + T) % S
		rev_edges[(m + T) % S] = m
	maxlenpath = 1
	visitted = defaultdict(int)
	for k in edges:
		if visitted[k]:
			continue
		counter = 0
		b = k
		while b in edges:
			counter += 1
			b = edges[b]
			if visitted[b]:
				print(-1)
				return
			else:
				visitted[b] = 1
		b = k
		while b in rev_edges:
			counter += 1
			b = rev_edges[b]
			if visitted[b]:
				print(-1)
				return
			else:
				visitted[b] = 1
		if maxlenpath < counter:
			maxlenpath = counter
	print(maxlenpath)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	s = next(tokens)
	t = next(tokens)
	solve(s, t)
main()


s = input()
t = input()
base = 3
MOD = 1004535809

def rolling_hash(s, base, MOD):
	l = len(s)
	h = [0] * (l + 1)
	for i in range(l):
		h[i + 1] = (h[i] * base + ord(s[i])) % MOD
	return h
s = s * ((len(t) + len(s) - 1) // len(s) * 2)
rh0 = rolling_hash(s, base, MOD)
B = 0
for c in t:
	B = (B * base + ord(c)) % MOD
N = len(s) // 2
M = len(t)
R = [0] * N
L = pow(base, M, MOD)
r = 0
for i in range(N):
	if (rh0[i + M] - rh0[i] * L) % MOD == B:
		R[i] = 1
if not any(R):
	print(0)
	return
S = []
for i in range(N):
	if R[i - M] and R[i] == 0:
		S.append((i - M) % N)
if not S:
	print(-1)
	return
ans = 0
for v in S:
	d = 1
	while R[v - M]:
		d += 1
		v = (v - M) % N
	ans = max(ans, d)
print(ans)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

class UnionFind(object):

	def __init__(self, n):
		self.__par = list(range(n))
		self.__rank = [0] * n
		self.__size = [1] * n

	def root(self, k):
		if self.__par[k] == k:
			return k
		self.__par[k] = self.root(self.__par[k])
		return self.__par[k]

	def unite(self, i, j):
		i = self.root(i)
		j = self.root(j)
		par = self.__par
		rank = self.__rank
		size = self.__size
		if i == j:
			return False
		if rank[i] > rank[j]:
			par[j] = i
			size[i] += size[j]
		else:
			par[i] = j
			size[j] += size[i]
			if rank[i] == rank[j]:
				rank[j] += 1
		return True

	def size(self, k):
		return self.__size[self.root(k)]

class RollingHash(object):
	__base1 = 1007
	__mod1 = 10 ** 9 + 9
	__base2 = 1009
	__mod2 = 10 ** 9 + 7

	def __init__(self, s):
		n = len(s)
		self.__s = s
		self.__n = n
		b1 = self.__base1
		m1 = self.__mod1
		b2 = self.__base2
		m2 = self.__mod2
		(H1, H2) = ([0] * (n + 1), [0] * (n + 1))
		(P1, P2) = ([1] * (n + 1), [1] * (n + 1))
		for i in range(n):
			H1[i + 1] = (H1[i] * b1 + ord(s[i])) % m1
			H2[i + 1] = (H2[i] * b2 + ord(s[i])) % m2
			P1[i + 1] = P1[i] * b1 % m1
			P2[i + 1] = P2[i] * b2 % m2
		self.__H1 = H1
		self.__H2 = H2
		self.__P1 = P1
		self.__P2 = P2

	def hash(self, l, r):
		m1 = self.__mod1
		m2 = self.__mod2
		assert 0 <= l <= r <= self.__n
		return ((self.__H1[r] - self.__P1[r - l] * self.__H1[l] % m1) % m1, (self.__H2[r] - self.__P2[r - l] * self.__H2[l] % m2) % m2)

def resolve():
	from math import ceil
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	s = s * ceil(m / n)
	s = s * 2
	ok = [0] * n
	uf = UnionFind(n)
	rhs = RollingHash(s)
	rht = RollingHash(t)
	t = rht.hash(0, m)
	for i in range(n):
		if rhs.hash(i, i + m) == t:
			ok[i] = 1
	for i in range(n):
		if ok[i] and ok[(i + m) % n]:
			if not uf.unite(i, (i + m) % n):
				print(-1)
				return
	ans = 0
	for i in range(n):
		if ok[i]:
			ans = max(ans, uf.size(i))
	print(ans)
resolve()


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
	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)
	if len(location_list) == 0:
		print(0)
		return
	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)
main()


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)


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 = [-1] * (len(s) + 1)
for (a, b) in kmp_search(m * s, t):
	(a, b) = (a % len(s) + 1, b % len(s) + 1)
	d[a] = b
ls = [-1] * (len(s) + 1)
vs = set()
for i in range(1, len(s) + 1):
	if i in vs:
		continue
	c = 0
	j = i
	while True:
		vs.add(i)
		i = d[i]
		if i == -1:
			break
		c += 1
		if i == j:
			c = inf
			break
		if ls[i] != -1:
			c += ls[i]
			break
	if c == inf:
		break
	ls[j] = c
print(max(ls) if c != inf else -1)


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)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
INF = float('inf')

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n
		self.size = [1] * n

	def root(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.root(self.table[x])
			return self.table[x]

	def get_size(self, x):
		r = self.root(x)
		return self.size[r]

	def is_same(self, x, y):
		if self.root(x) == self.root(y):
			return True
		else:
			return False

	def unite(self, x, y):
		r1 = self.root(x)
		r2 = self.root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			self.size[r1] += self.size[r2]
			if d1 == d2:
				self.table[r1] -= 1
		else:
			self.table[r1] = r2
			self.size[r2] += self.size[r1]

def z_algorithm(S):
	l = len(S)
	A = [0] * l
	i = 1
	j = 0
	while i < l:
		while i + j < l and S[j] == S[i + j]:
			j += 1
		if not j:
			i += 1
			continue
		A[i] = j
		k = 1
		while l - i > k < j - A[k]:
			A[i + k] = A[k]
			k += 1
		i += k
		j -= k
	return A
s = S()
t = S()
s_len = len(s)
t_len = len(t)
if s_len < t_len:
	s *= t_len // s_len + 1
s *= 2
A = z_algorithm(t + '?' + s)[t_len + 1:]
graph = [[] for _ in range(s_len)]
U = UnionFind(s_len)
flag = False
for i in range(s_len):
	if A[i] == t_len:
		if U.is_same(i, (i + t_len) % s_len):
			flag = True
			break
		U.unite(i, (i + t_len) % s_len)
if flag:
	print(-1)
else:
	print(max(U.size) - 1)


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)


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))
main()


def search_rolling_hash(S, T):
	base = 1234
	mod = 10 ** 9 + 7
	(n, m) = (len(S), len(T))
	rolling_hash = [0] * (n - m + 1)
	rolling_hash[0] = ord(S[0])
	b_m = pow(base, m, mod)
	T_hash = ord(T[0])
	start_index = []
	for i in range(1, m):
		rolling_hash[0] *= base
		rolling_hash[0] += ord(S[i])
		rolling_hash[0] %= mod
		T_hash = (T_hash * base + ord(T[i])) % mod
	if rolling_hash[0] == T_hash:
		start_index.append(0)
	for i in range(1, ls):
		rolling_hash[i] = (rolling_hash[i - 1] * base - ord(S[i - 1]) * b_m + ord(S[i + m - 1])) % mod
		if rolling_hash[i] == T_hash:
			start_index.append(i)
	return start_index
import sys
s = input()
t = input()
(ls, lt) = (len(s), len(t))
S = s * (lt // ls + 2)
index = search_rolling_hash(S, t)
flag = [False] * ls
for i in index:
	flag[i] = True
stack = []
inf = float('inf')
cnt = [inf] * ls
for i in range(ls):
	if flag[i] == False:
		stack.append(i)
		cnt[i] = 0
while stack:
	x = stack.pop()
	y = (x - lt) % ls
	if cnt[y] == inf:
		cnt[y] = cnt[x] + 1
		stack.append(y)
ans = max(cnt)
if ans == inf:
	print(-1)
else:
	print(ans)


def RollingHash(S, T, ls):
	if len(S) < len(T):
		return []
	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)


from math import ceil

def zalgo(S):
	L = len(S)
	Z = [0] * L
	l = 0
	for i in range(1, L):
		if i + Z[i - l] < l + Z[l]:
			Z[i] = Z[i - l]
		else:
			cnt = max(0, l + Z[l] - i)
			while i + cnt < L and S[i + cnt] == S[cnt]:
				cnt += 1
			Z[i] = cnt
			l = i
	Z[0] = L
	return Z

def topological_sort(E, D):
	D = D[:]
	n = len(E)
	Q = [i for i in range(n) if D[i] == 0]
	L = []
	while Q:
		p = Q.pop()
		L.append(p)
		for vf in E[p]:
			D[vf] -= 1
			if not D[vf]:
				Q.append(vf)
	if len(L) != n:
		return False
	return L
S = [ord(s) - 97 for s in input().strip()]
T = [ord(t) - 97 for t in input().strip()]
ls = len(S)
lt = len(T)
S = S * ceil(lt / ls)
ls = len(S)
Z = zalgo(T + [-1] + S + S)[lt + 1:]
Edge = [[] for _ in range(ls)]
Dim = [0] * ls
for i in range(ls):
	if Z[i] == lt:
		Edge[i] = [(i + lt) % ls]
		Dim[(i + lt) % ls] += 1
TS = topological_sort(Edge, Dim)
if TS == False:
	print(-1)
else:
	dp = [0] * ls
	for ts in TS:
		if Edge[ts]:
			dp[Edge[ts][0]] = 1 + dp[ts]
	print(max(dp))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
MOD = 10 ** 9 + 993
base = 123450
S = np.array([ord(x) for x in input().rstrip()], dtype=np.int64)
T = np.array([ord(x) for x in input().rstrip()], dtype=np.int64)
LS = len(S)
LT = len(T)
n = (LT + -LT % LS) // LS
S = np.concatenate([S] * (n + 1))
S = S[:LS + LT]

def cumprod(arr):
	L = len(arr)
	Lsq = int(L ** 0.5 + 1)
	arr = np.resize(arr, Lsq ** 2)
	arr = arr.reshape(Lsq, Lsq)
	for n in range(1, Lsq):
		arr[:, n] *= arr[:, n - 1]
		arr[:, n] %= MOD
	for n in range(1, Lsq):
		arr[n] *= arr[n - 1, -1]
		arr[n] %= MOD
	return arr.ravel()[:L]
base_inv = pow(base, MOD - 2, MOD)
x = np.full(LS + LT, base, dtype=np.int64)
x[0] = 1
power = cumprod(x)
x = np.full(LS + LT, base_inv, dtype=np.int64)
x[0] = 1
power_inv = cumprod(x)

def to_rolling_hash(S):
	return (S * power[:len(S)] % MOD).cumsum() % MOD
S_hash = to_rolling_hash(S)
T_hash = to_rolling_hash(T)[-1]
S_hash_LT = S_hash[LT - 1:]
S_hash_LT[1:] -= S_hash.copy()[:LS]
S_hash_LT %= MOD
S_hash_LT *= power_inv[:LS + 1]
S_hash_LT %= MOD
INF = 10 ** 18
visited = [False] * LS
dist = [INF] * LS
q = np.where(S_hash_LT[:LS] != T_hash)[0].tolist()
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)


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)


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)


from collections import deque

def gcd(m, n):
	r = m % n
	return gcd(n, r) if r else n
s = input()
t = input()

class RollingHash:

	def __init__(self, s, base, MOD):
		self.s = s
		self.l = l = len(s)
		self.base = base
		self.MOD = MOD
		self.h = h = [0] * (l + 1)
		for i in range(l):
			h[i + 1] = (h[i] * base + ord(s[i])) % MOD

	def get(self, l, r):
		MOD = self.MOD
		return (self.h[r] - self.h[l] * pow(self.base, r - l, MOD) + MOD) % MOD
base = 3
g = gcd(len(s), len(t))
s = s * ((len(t) + len(s) - 1) // len(s))
MOD = 1004535809
rh0 = RollingHash(s, base, MOD)
rh1 = RollingHash(t, base, MOD)
N = len(s)
M = len(t)
B = rh1.get(0, M)
R = [0] * N
r = 0
for i in range(N - M + 1):
	if rh0.get(i, i + M) == B:
		R[i] = r = 1
for i in range(N - M + 1, N):
	if (rh0.get(i, N) * pow(base, M - (N - i), MOD) + rh0.get(0, M - (N - i))) % MOD == B:
		R[i] = r = 1
if not r:
	print(0)
	exit(0)
D = [0] * N
que = deque()
for i in range(N):
	if R[i] and R[(i + M) % N] == 0:
		que.append(i)
		D[i] = 1
if not que:
	print(-1)
	exit(0)
while que:
	v = que.popleft()
	if R[v - M]:
		que.append((v - M) % N)
		D[v - M] = D[v] + 1
print(max(D))