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.



Sample input:
abcabab
ab


Sample output:
3

Submission status: Accepted

Solution code:
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:
    # graph[node] = [(cost, to)]
    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 )
    # print(graph)

    ts = topological_sort(graph, n0)
    if len(ts) != n0:
        ans = -1
    else:
        # print(ts)
        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()

Submission status: Accepted

Solution code:
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:
    # graph[node] = [(cost, to)]
    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:]
    # print(z)

    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:
        # print(ts)
        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()

Submission status: Accepted

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

import numpy as np

# 適当な素数と原始根でrolling hash
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)

# Sの方が長くする
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def f_strings_of_eternity(S, T):
    # 参考: https://atcoder.jp/contests/abc135/submissions/6579342

    # Sの方がTより長いようにする(sはSの整数倍の長さというわけではない)
    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

    # 基数 base, mod MOD 上での冪乗テーブルの構成
    MOD = 10 ** 16 + 61  # 大きな素数(2**64 だとハッシュが衝突するような入力がある)
    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')
    # [k]: 元の文字列Sについて、Sの先頭k文字目からTが一致するか
    can_start = [(hash_s[i + length_t - 1] - hash_s[i - 1]) * power_inv[i] %
                 MOD == hash_t for i in range(length_s)]
    # [k]: sの先頭k文字目から開始したとき、tが何回連続した文字列が現れるか
    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

    # 基本的に max(num_continuation) が解だが、それが無限大のときは特別扱いする
    ans = max(num_continuation)
    return ans if ans != INF else -1

S = input()
T = input()
print(f_strings_of_eternity(S, T))

Submission status: Accepted

Solution code:
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)
    # 最大は, (n-1)+m 
    # kn >= (n-1)+m
    # k >= 1 +(m-1)/n
    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)
    # loopを見つける
    # start地点をすべて試す
    # 進む方向、戻る方向について別々に求める
    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()

Submission status: Accepted

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

# Same character goes to infinity
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)

Submission status: Accepted

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

# Same character goes to infinity
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)

Submission status: Accepted

Solution code:
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

#sを伸ばす
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)

    # Sの方が長くなるように
    if T > S:
        s *= int(math.ceil(T/S))

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    # グラフを構成し、最長パスが答え。ループがあれば-1
    # グラフは辞書で表現
    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:
        # kが含まれるパスを考える。
        # 逆向きにはったグラフを利用して、双方向の長さを求める
        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
        # print("visitted: ", visitted)
        # print("counter: ", counter)
        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)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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:
                # スタート地点が重なることもあるから、+=ではなく=1にする
                # 複数あることは絶対にないので
                ret[(i-self.n+1)%n] = 1 
        return ret

def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    # 最大は, (n-1)+m 
    # kn >= (n-1)+m
    # k >= 1 +(m-1)/n
    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)
    # loopを見つける
    # start地点をすべて試す
    # 進む方向、戻る方向について別々に求める
    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()

Submission status: Accepted

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