Problem:
 Score : 600 points    Problem Statement Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.   There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s .       Notes   A string a is a substring of another string b if and only if there exists an integer x  (0 \leq x \leq |b| - |a|) such that, for any y  (1 \leq y \leq |a|) , a_y = b_{x+y} holds.    We assume that the concatenation of zero copies of any string is the empty string. From the definition above, the empty string is a substring of any string. Thus, for any two strings s and t , i = 0 satisfies the condition in the problem statement.        Constraints  1 \leq |s| \leq 5 \times 10^5  1 \leq |t| \leq 5 \times 10^5  s and t consist of lowercase English letters.         Input Input is given from Standard Input in the following format:  s  t       Output If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i ; if the number is infinite, print -1 .        Sample Input 1 abcabab
ab      Sample Output 1 3  The concatenation of three copies of t , ababab , is a substring of the concatenation of two copies of s , abcabababcabab , so i = 3 satisfies the condition.  On the other hand, the concatenation of four copies of t , abababab , is not a substring of the concatenation of any number of copies of s , so i = 4 does not satisfy the condition.  Similarly, any integer greater than 4 does not satisfy the condition, either. Thus, the number of non-negative integers i satisfying the condition is finite, and the maximum value of such i is 3 .       Sample Input 2 aa
aaaaaaa      Sample Output 2 -1  For any non-negative integer i , the concatenation of i copies of t is a substring of the concatenation of 4i copies of s . Thus, there are infinitely many non-negative integers i that satisfy the condition.       Sample Input 3 aba
baaab      Sample Output 3 0  As stated in Notes, i = 0 always satisfies the condition.

Solution (Python):
import sys
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):
    """
    xの親ノードを返す
    """
    if self.parent[x] != x:
      self.parent[x] = self.root(self.parent[x])  
    return self.parent[x]

  def union(self, x, y):
    """
    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)


if __name__ == '__main__':
  main()

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

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

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

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

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

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

S = []
for i in range(N):
    if R[i-M] and R[i] == 0:
        S.append((i - M) % N)
if not S:
    print(-1)
    exit(0)

ans = 0
for v in S:
    d = 1
    while R[v-M]:
        d += 1
        v = (v - M) % N
    ans = max(ans, d)
print(ans)

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
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):
        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) * 2) // len(s)
t = t * 3
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)

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

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

Solution (Python):

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


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    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="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    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)


if __name__ == '__main__':
    main()

Solution (Python):
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_table()

    def create_table(self):
        table = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = table[j]
            j += 1
            table[i+1] = j
        self.table = table

    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.table[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)

if __name__ == "__main__":
    main()

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

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

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

for i in range(len(s)):
    j = (i+len(t))%len(s)
    if z[i] == len(t) and z[j] == len(t):
        u.union(i,j)

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:
    loop = True
    if len(d[k])==1:
        loop = len(t)%len(s)==0
    else:
        for i in d[k]:
            j = (i+len(t)*(len(d[k])-1))%len(s)
            loop = z[j]==len(t) and loop
    if loop:
        ans = -1
        break
    ans = max(ans,len(d[k]))

print(ans)

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