提出 #6575399

---

ソースコード 拡げる

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

S = input().rstrip()
T = input().rstrip()

S,T

# Sの方が長くする
LS = len(S)
LT = len(T)
n = (LT + (-LT) % LS) // LS
S *= (n+1)
S = S[:LS+LT]

MOD = 10 ** 16 + 61
base = 12345
base_inv = pow(base,MOD-2,MOD) 
power = [1] * (LS+LT)
power_inv = [1] * (LS+LT)
for n in range(1,LS+LT):
    power[n] = power[n-1] * base % MOD
    power_inv[n] = power_inv[n-1] * base_inv % MOD

def to_rolling_hash(S):
    ret = [0] * len(S)
    for i,s in enumerate(S):
        ret[i] = (ret[i-1] + power[i] * ord(s)) % MOD
    return ret

S_hash = to_rolling_hash(S) + [0]
T_hash = to_rolling_hash(T)[-1] # 文字列全体

can_start = [(S_hash[i + LT - 1] - S_hash[i - 1]) * power_inv[i] % MOD == T_hash for i in range(LS)]

INF = 10 ** 18
visited = [False] * LS
dp = [None] * LS

def dfs(i):
    if visited[i]:
        if dp[i] is None:
            # ループ
            return INF
        return dp[i]
    visited[i] = True
    if not can_start[i]:
        dp[i] = 0
        return 0
    x = dfs((i + LT) % LS) + 1
    dp[i] = x
    return x

answer = max(dfs(i) for i in range(LS))

if answer >= INF:
    answer = -1

print(answer)

提出情報

ジャッジ結果