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

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

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

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

Solution (Python):

def search_rolling_hash(S, T):
    base = 1234
    mod = 2**64-1
    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)

Solution (Python):

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)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

S = np.array(list(readline().rstrip()),np.int64)
T = np.array(list(readline().rstrip()),np.int64)

LS = len(S); LT = len(T)
LSext = LS + LT
LSext += (-LSext) % LS
Sext = np.tile(S,LSext//LS)

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).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]

U = 2*10**6
MOD = 10 ** 9 + 993
base = 123450
x = np.full(U,base,dtype=np.int64); x[0] = 1
power = cumprod(x,MOD)
x = np.full(U,pow(base,MOD-2,MOD),dtype=np.int64); x[0] = 1
power_inv = cumprod(x,MOD)

def RollingHash(S):
    return (S * power[:len(S)] % MOD).cumsum() % MOD

Sext_hash = RollingHash(Sext)
T_hash = RollingHash(T)[-1]


x = Sext_hash[LT-1:LS+LT-1].copy()
x[1:] -= Sext_hash[:LS-1]
x *= power_inv[:LS]; x %= MOD


INF = LS+100
cnt = [INF] * LS
stack = np.where(x!=T_hash)[0].tolist()
for x in stack:
    cnt[x] = 0
while stack:
    x = stack.pop()
    y = (x-LT)%LS
    if cnt[y] == INF:
        cnt[y] = cnt[x] + 1
        stack.append(y)

answer = max(cnt)
if answer == INF:
    answer = -1
print(answer)

Solution (Python):
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)
    while len(s) < m + n:
        s += s
    a = KMP(t)
    b = a.match(s)
    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
     

if __name__ == "__main__":
    print(main())

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

if __name__ == "__main__":
    print(main())

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































            
    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
    return ans

if __name__ == "__main__":
    print(main())

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

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

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

Solution (Python):
def kmp(s):
    n = len(s)
    kmp = [0] * (n+1)
    kmp[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and s[i] != s[j]:
            j = kmp[j]
        j += 1
        kmp[i+1] = j

    return kmp

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)

    res = kmp(t + '*' + s)
    res = res[m+2:]

    graph = [set() for _ in range(n0)]
    for i in range(len(res)):
        if res[i] >= m:
            graph[(i-m+1)%n0].add( (i + 1) % 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()

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

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

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