公式
E - リピート再生と部分一致 / Repeat Playback and Partial Matching 解説 by admin
Claude 4.6 Opus (Thinking)概要
文字列 \(S\) を無限に繰り返した文字列 \(S^{\infty}\) から切り出した部分文字列 \(T_i\) が、元の文字列 \(S\) の連続部分文字列として出現するかどうかを各クエリについて高速に判定する問題です。
考察
基本的な観察
\(S^{\infty}\) は周期 \(N\) の文字列なので、\(T_i\) の開始位置は \(\text{start} = (L_i - 1) \bmod N\)（0-indexed）で決まります。\(T_i\) の長さを \(\text{length} = R_i - L_i + 1\) とすると：
- \(\text{length} > N\) の場合: \(S\) の長さは \(N\) なので、長さ \(N\) を超える部分文字列は \(S\) に含まれ得ません。答えは
No。 - \(\text{start} + \text{length} \leq N\) の場合: \(T_i = S[\text{start} : \text{start}+\text{length}]\) でそのまま \(S\) の部分文字列です。答えは
Yes。 - \(\text{start} + \text{length} > N\) の場合（ラップアラウンド）: \(T_i\) は \(S\) の末尾部分 \(S[\text{start}:N]\) と先頭部分 \(S[0:\text{end}]\) を連結したものになります。ここで \(\text{tail} = N - \text{start}\)、\(\text{end} = \text{length} - \text{tail}\) です。
ラップアラウンドの場合の分析
\(T = S[\text{start}:N] + S[0:\text{end}]\) が \(S\) のどこかに出現するか調べたいです。つまり、ある位置 \(p\) で \(S[p:p+\text{length}]\) が \(T\) と一致するか判定します。
この一致を 分割点 \(j = p + \text{tail}\) で考えます。\(j\) は \(S\) 内で「末尾部分の一致が終わり、先頭部分の一致が始まる」境界です。条件は：
- \(S[p:j] = S[\text{start}:N]\)（\(S\) の末尾 \(\text{tail}\) 文字と一致）
- \(S[j:j+\text{end}] = S[0:\text{end}]\)（\(S\) の先頭 \(\text{end}\) 文字と一致）
- \(j \in [\text{tail},\ N - \text{end}]\)（範囲内であること）
Z関数の活用
- 条件2 は \(S\) の Z関数 で判定できます。\(Z[j]\) は「\(S\) と \(S[j:]\) の最長共通接頭辞の長さ」なので、\(Z[j] \geq \text{end}\) が条件2です。
- 条件1 は 逆Z関数（\(S\) を反転した文字列の Z関数）で判定できます。\(R = \text{reverse}(S)\) の Z関数 \(Z_R\) を用いると、\(Z_R[N-j]\) は「\(S\) の位置 \(j\) で終わる部分と \(S\) の末尾がどれだけ一致するか」を表します。\(Z_R[N-j] \geq \text{tail}\) が条件1です。
- 条件3 は条件1,2に自然に含まれます（\(j \geq \text{tail}\) は \(\min(j, Z_R[N-j]) \geq \text{tail}\) に、\(j \leq N-\text{end}\) は \(\min(Z[j], N-j) \geq \text{end}\) に含まれる）。
2次元支配問題への帰着
各分割点 \(j\)（\(1 \leq j \leq N-1\)）に対して： $\(b_j = \min(j,\ Z_R[N-j]), \quad a_j = \min(Z[j],\ N-j)\)$
と定義すると、クエリ \((\text{tail}, \text{end})\) の答えは：
\(b_j \geq \text{tail}\) かつ \(a_j \geq \text{end}\) を満たす \(j\) が存在するか？
これは2次元の支配問題です。関数 \(f(t) = \max\{a_j \mid b_j \geq t\}\) を前計算すれば、各クエリは \(f(\text{tail}) \geq \text{end}\) の判定だけで済みます。
\(f\) は以下のように \(O(N)\) で計算できます： 1. 配列 \(g[t] = \max\{a_j \mid b_j = t\}\) を計算 2. \(f[t] = \max(g[t],\ f[t+1])\) と右から累積最大値を取る
アルゴリズム
- \(S\) の Z関数 \(Z\) を計算する。
- \(R = \text{reverse}(S)\) の Z関数 \(Z_R\) を計算する。
- 各 \(j = 1, \ldots, N-1\) に対し \(b_j = \min(j, Z_R[N-j])\)、\(a_j = \min(Z[j], N-j)\) を計算。
- 配列 \(g\) に \(g[b_j] = \max(g[b_j], a_j)\) を格納し、右からの累積最大値で \(f\) を構築。
- 各クエリに対し：
- \(\text{length} > N\) →
No - \(\text{start} + \text{length} \leq N\) →
Yes（ラップなし） - ラップアラウンド → \(f[\text{tail}] \geq \text{end}\) なら
Yes、そうでなければNo
- \(\text{length} > N\) →
計算量
- 時間計算量: \(O(N + Q)\)（Z関数の計算が \(O(N)\)、\(f\) の構築が \(O(N)\)、各クエリが \(O(1)\)）
- 空間計算量: \(O(N)\)
実装のポイント
\(L_i, R_i\) が最大 \(10^{18}\) と非常に大きいため、開始位置の計算には \(\bmod N\) を使う。Python は多倍長整数を扱えるので溢れの心配は不要。
Z関数は標準的な線形アルゴリズムで実装する。\(Z[0] = N\)（文字列全体が自身の接頭辞）と定義する。
\(f\) の配列を構築する際、\(b_j \geq 1\) かつ \(a_j \geq 1\) の \(j\) のみが有効（\(\text{tail}, \text{end} \geq 1\) なので）。
ラップアラウンドが起こるのは \(\text{start} \geq 1\) かつ \(\text{end} \geq 1\) の場合のみ。\(\text{start} = 0\) でラップが起きるなら \(\text{length} > N\) となり、既に
Noと判定済み。ソースコード
import sys
from math import gcd
def solve():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
Q = int(input_data[idx]); idx += 1
S = input_data[idx].decode(); idx += 1
# We need to determine for each query (L, R):
# T_i is the substring of S^inf from position L to R.
# We need to check if T_i appears as a contiguous substring of S.
# Key observations:
# - If R - L + 1 > N, answer is No.
# - If R - L + 1 <= N, T_i is a substring of S+S (since S^inf has period N).
# Specifically, T_i starts at position ((L-1) % N) in S+S (0-indexed).
# T_i = (S+S)[start : start + length] where start = (L-1) % N, length = R - L + 1.
# This is a substring of S+S of length <= N.
# We need to check if this substring appears somewhere within S (positions 0..N-1,
# i.e., as (S)[p : p+length] for some 0 <= p <= N - length).
# If start + length <= N, then T_i = S[start : start+length], which is already a substring of S. Answer: Yes.
# If start + length > N, then T_i wraps around. T_i = S[start:] + S[:end] where end = (start + length) - N.
# We need to check if this concatenation appears as a substring of S.
# For the wrapping case, T_i = S[start:N] + S[0:end] where end = start + length - N.
# This is a string of length = (N - start) + end = length.
# We need: does there exist p in [0, N-length] such that S[p:p+length] == S[start:N] + S[0:end]?
# Using Z-function or string matching on carefully constructed strings.
#
# Alternative approach using the "failure function" / Z-function:
# Consider the string S + S. Any T_i (when length <= N) is a substring of S+S.
# We need to check if that substring of S+S also appears within the first N characters of S+S (i.e., within S).
#
# For the non-wrapping case (start + length <= N): it's trivially in S. Answer: Yes.
# For the wrapping case: T = S[start:] + S[:end]. We need to find this pattern in S.
#
# Key insight using the period structure:
# T wraps around, meaning it's S[start:N] + S[0:end].
# For T to appear at position p in S: S[p..p+len-1] = S[start..N-1] + S[0..end-1].
# This means S[p..p+(N-start)-1] = S[start..N-1] AND S[p+(N-start)..p+len-1] = S[0..end-1].
# Second condition: S[p+(N-start)+j] = S[j] for j=0..end-1, which means position p+(N-start)
# is a place where S "restarts", i.e., S[p+(N-start)..p+(N-start)+end-1] = S[0..end-1].
# Use Z-function of S: Z[i] = length of longest common prefix of S and S[i:].
# Condition: exists p in [0, N-length] such that:
# 1) S[p : p+(N-start)] = S[start : N] (suffix of S starting at 'start' matches at position p)
# 2) Z[p + (N - start)] >= end (at position p+(N-start), at least 'end' chars match prefix of S)
# Also need: p + (N-start) <= N (so that index is valid for Z), and p+(N-start) can be 0 only if p=0 and start=0 (non-wrapping).
# For condition 1: S[p..p+tail-1] = S[start..N-1] where tail = N - start.
# Build Z-function of reverse(S) to find suffix matches, or use a different construction.
# Actually, let's build the Z-function of the string: S[start:] + '#' + S. Then positions after '#' where Z >= tail indicate matches.
# But start varies per query... We need a general approach.
# Let me use hashing for O(1) substring comparison.
MOD1 = (1 << 61) - 1
BASE1 = 131
n = N
h = [0] * (n + 1)
pw = [1] * (n + 1)
for i in range(n):
h[i+1] = (h[i] * BASE1 + ord(S[i])) % MOD1
pw[i+1] = pw[i] * BASE1 % MOD1
def get_hash(l, r): # 0-indexed [l, r)
return (h[r] - h[l] * pw[r - l]) % MOD1
# Z-function of S
Z = [0] * n
Z[0] = n
l = r = 0
for i in range(1, n):
if i < r:
Z[i] = min(r - i, Z[i - l])
while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
Z[i] += 1
if i + Z[i] > r:
l, r = i, i + Z[i]
# Suffix Z: for each position i, longest match of S[i:] with S[N-k:] (suffix matching)
# We need: for condition 1, S[p:p+tail] == S[start:N], i.e., a suffix of S starting at 'start'.
# Let's build "suffix array" style: reverse Z-function.
# Let R = reverse(S). ZR = Z-function of R.
# ZR[i] gives longest common prefix of R and R[i:], which corresponds to longest common suffix of S ending at position N-1-i in S...
# Actually let me think differently.
# For each query with wrapping, we need to check:
# exists p in [0, N-length] such that S[p:p+length] has hash equal to hash of T.
# T's hash = hash(S[start:N]) concatenated with hash(S[0:end]).
# T_hash = get_hash(start, N) * pw[end] + get_hash(0, end)) % MOD1
# We need: exists p such that get_hash(p, p+length) == T_hash.
# This is O(N) per query which is too slow.
# Better: use the structure. T = S[start:N] + S[0:end].
# Let tail = N - start, so length = tail + end.
# We need p such that:
# S[p:p+tail] == S[start:N] AND S[p+tail:p+tail+end] == S[0:end]
#
# Condition 2: S[p+tail : p+tail+end] == S[0:end], means Z[p+tail] >= end (if p+tail > 0), or p+tail==0 which means p=0,tail=0 impossible since tail>=1.
# Actually p+tail can equal 0 only if p=0 and tail=0, but tail = N-start >= 1 since start < N.
# If p+tail = N, that's out of bounds for Z. But p+tail <= p+length <= N, and p+tail = N means end=0 which contradicts wrapping.
# So p+tail < N always in wrapping case.
# Condition 2: Z[p+tail] >= end.
# Condition 1: S[p:p+tail] == S[start:N]. Use hashing: get_hash(p, p+tail) == get_hash(start, N).
#
# Precompute for each position j (1<=j<N): the set of positions where Z[j] >= some value.
# We want: for given (start, end, tail=N-start, length=tail+end):
# exists p in [0, N-length] such that Z[p+tail] >= end AND get_hash(p, p+tail) == get_hash(start, N).
# p+tail ranges over [tail, N-length+tail] = [tail, N-end].
# So we need j in [tail, N-end] with Z[j] >= end and get_hash(j-tail, j) == get_hash(start, N).
# i.e., S[j-tail:j] == S[start:N], which is S[j-tail:j] == S[N-tail:N].
# S[j-tail:j] == S[N-tail:N] means the tail characters ending at position j-1 match the last tail characters of S.
# Define: for each position j in S (1-indexed end), let suffmatch[j] = length of longest match of S[..j-1] suffix with S's suffix.
# More precisely, let's define using reverse Z:
# Let R = S reversed. ZR = Z-function of R.
# ZR[i] for R means: longest common prefix of R and R[i:].
# R[i:] reversed = S[0:N-i], R reversed = S.
# Common prefix of R and R[i:] of length k means R[0:k] == R[i:i+k],
# which means S[N-k:N] == S[N-i-k:N-i].
# So S[N-i-k:N-i] == S[N-k:N] with k = ZR[i].
# In other words, the substring of S ending at position N-i-1 (0-indexed) of length ZR[i] matches the suffix of S of the same length.
# We need: S[j-tail:j] == S[N-tail:N], i.e., substring ending at position j-1 of length tail matches suffix of S of length tail.
# Using the reverse Z result: let i' be such that N - i' = j, so i' = N - j.
# Then ZR[i'] = ZR[N-j] gives the longest match. We need ZR[N-j] >= tail.
# So condition 1 becomes: ZR[N-j] >= tail, where j in [tail, N-end].
# Combined: Z[j] >= end AND ZR[N-j] >= tail, j in [tail, N-end].
# Note j=0 would mean ZR[N]=tail, but ZR has indices 0..N-1, so j<N always (since end>=1, j<=N-end<=N-1).
# j=N-end: need Z[N-end]>=end. Z[0]=N>=end always, but j=N-end, if N-end=0 then j=0, Z[0]=N>=end=N, ok. And ZR[N-0]=ZR[N] which is out of bounds...
# Actually j ranges [tail, N-end]. If tail=0, that means start=N which won't happen.
# j can be 0 only if tail=0. Since we're in wrapping case, start>=1 (otherwise start=0 and start+length>N means length>N, already handled). Actually start = (L-1)%N, could be 0. If start=0, then tail=N, length=N+end>N, but we already check length<=N, so end<=0, contradiction. So start>=1, tail<=N-1, j>=tail>=1. Good.
# N-j: j<=N-end, so N-j>=end>=1. j>=tail>=1, so N-j<=N-1. So N-j in [1,N-1], valid for ZR.
R = S[::-1]
ZR = [0] * n
ZR[0] = n
l = r = 0
for i in range(1, n):
if i < r:
ZR[i] = min(r - i, ZR[i - l])
while i + ZR[i] < n and R[ZR[i]] == R[i + ZR[i]]:
ZR[i] += 1
if i + ZR[i] > r:
l, r = i, i + ZR[i]
# For each j in [1, N-1], we have Z[j] and ZR[N-j].
# For a query with (tail, end) where tail+end<=N, tail>=1, end>=1:
# We need: exists j in [tail, N-end] with Z[j]>=end and ZR[N-j]>=tail.
# This is still potentially O(N) per query in worst case if we scan.
# We need a smarter approach.
# Observation: ZR[N-j] >= tail = N-start means the suffix match at position j is long enough.
# Let's define for each j: a[j] = Z[j] (prefix match length), b[j] = ZR[N-j] (suffix match length).
# We need: exists j in [tail, N-end] with a[j] >= end and b[j] >= tail.
# Since tail + end = length, and length <= N, we have tail = length - end.
# Actually tail = N - start, end = start + length - N. And length = R-L+1.
# Alternative: note that a[j] + b[j] tells us something. If a[j] + b[j] >= N, then S is periodic
# in a certain sense. But in general this doesn't hold.
# Let me think about it differently.
# Condition: a[j] >= end AND b[j] >= tail, with j in [tail, N-end].
# Note that j >= tail and b[j] >= tail: b[j] >= tail means the suffix of S of length tail matches
# at a certain position. The set of j where b[j] >= tail is determined by the suffix structure.
# For efficiency, let's precompute for each j the value a[j] + b[j], and also precompute
# range-max or similar structures. But the constraints are 2D (a[j]>=end, b[j]>=tail, j in range).
# Let me try: group queries. For each j, it can answer queries where tail <= j, end <= a[j], tail <= b[j], end <= N-j.
# i.e., tail <= min(j, b[j]) and end <= min(a[j], N-j).
# Since tail + end = length <= N, and we want the existence of ANY such j...
# Key insight: if a[j] + b[j] >= length for some valid j, then we might be able to split.
# Actually: we need a[j] >= end and b[j] >= tail. Given a[j] and b[j], the set of (tail,end) pairs
# with tail+end=length that are satisfied is: tail <= b[j] and end <= a[j], i.e.,
# length - a[j] <= tail <= b[j], which requires length <= a[j] + b[j].
# Also j must be in [tail, N-end] = [tail, N-length+tail], i.e., tail in [max(1,j-?), ...].
# Actually j in [tail, N-end]: tail <= j and j <= N-end = N-length+tail, so tail >= j-N+length = j-(N-length).
# So tail in [max(1, j-(N-length)), j] intersected with [length-a[j], b[j]].
# This is getting complex. Let me try a different approach entirely.
# Approach: for each j from 1 to N-1, define c[j] = Z[j] + ZR[N-j].
# If c[j] >= N, then for ANY wrapping query with length <= N where j is in [tail, N-end]:
# Since a[j]+b[j] >= N >= length = tail+end, and we need tail<=b[j], end<=a[j]:
# a[j] >= N - b[j], so a[j] >= N - b[j]. We need a[j]>=end=length-tail and b[j]>=tail.
# If a[j]+b[j]>=N>=length, then for tail = min(b[j], j) ... hmm still complicated.
# Let me try the offline approach with sorting.
# For each j in [1, N-1], we have (b[j], a[j]) meaning it can handle queries with tail<=b[j] and end<=a[j].
# Also j must be in [tail, N-end], i.e., tail <= j <= N-end, i.e., tail <= j and tail >= j-(N-length).
# Given tail and end (with tail+end=length), j in [tail, N-end]=[tail, N-end].
#
# For a query (tail, end): answer is Yes iff exists j in [tail, N-end] with Z[j]>=end and ZR[N-j]>=tail.
# Offline approach:
# Sort queries by 'end' in increasing order.
# For each threshold 'end', the set of valid j's has Z[j] >= end. As 'end' increases, fewer j's are valid.
# Among valid j's (Z[j]>=end), we need one in [tail, N-end] with ZR[N-j]>=tail.
#
# Hmm, we need ZR[N-j] >= tail AND j >= tail AND j <= N-end.
# This is a 2D range query which is hard.
# Let me try yet another approach.
# For the wrapping case, T = S[start:] + S[:end].
# Build the string P = S + '#' + S + S. Then T appears in S iff T appears in the first N characters of P.
# But T varies per query...
# Actually, let's think about it as: T is a substring of SS = S+S starting at position 'start' with length 'length'.
# We want to know if T appears in S, i.e., appears in SS at some position p with p+length <= N.
# So we want: the substring SS[start:start+length] appears at some position in S.
#
# This is equivalent to: in the string SS, do the substrings SS[start:start+length] and SS[p:p+length]
# match for some p in [0, N-length]?
#
# Using suffix array of SS (length 2N), we can answer "does this substring appear at any position in [0, N-length]?"
# This is a classic problem: given a suffix array, for a query substring, find its range in the SA,
# then check if any suffix in that range starts at position <= N-length.
# SA of SS has length 2N. For each query, find the range [lo, hi] in SA where the substring SS[start:start+length] matches,
# then check if min of starting positions in SA[lo:hi+1] is <= N-length.
# With sparse table for range-min, this is O(1) per query after O(N log N) preprocessing.
# Building SA of length 2N where N can be 5*10^5: SA of length 10^6, feasible with SA-IS or DC3 in O(N).
# In Python, building SA might be slow... Let me try with the doubling approach.
# Actually, let's use a simpler approach. We can build the suffix array of S + S using the doubling method.
# But in Python, for N up to 5*10^5, SS has length 10^6. Suffix array construction in Python might be too slow.
# Let me think about using hashing instead.
# For each query: we have T = SS[start:start+length]. We want to check if T appears in S.
# We can compute the hash of T, then check against all substrings of S of the same length.
# But that's O(N) per query.
# With some precomputation: for each length l, store all hashes of substrings of S of length l in a set.
# But l can vary per query, and there are up to N distinct lengths, each with up to N hashes.
# Total storage O(N^2), too much.
# OK here's another idea that might work:
#
# For the wrapping case, we need j in [1, N-1] such that:
# Z[j] >= end AND ZR[N-j] >= tail AND j >= tail AND j <= N - end
#
# Let's define for each j: the "coverage" is the set of (tail, end) pairs it satisfies.
# tail <= min(j, ZR[N-j]) and end <= min(Z[j], N-j).
# So the maximum length it can handle is min(j, ZR[N-j]) + min(Z[j], N-j).
#
# For a given query, we need any j that covers it.
#
# Let me define: for each j, let bj = min(j, ZR[N-j]) and aj = min(Z[j], N-j).
# Then j satisfies the query (tail, end) iff tail <= bj and end <= aj.
# The query is answerable iff exists j with tail <= bj and end <= aj.
# This is a dominance query: given a set of points (bj, aj), does any point dominate (tail, end)?
# i.e., exists (bj, aj) with bj >= tail and aj >= end.
# This is equivalent to: max(aj : bj >= tail) >= end.
#
# So if we sort the points by bj in decreasing order and compute prefix max of aj,
# or equivalently, define f(tail) = max(aj : bj >= tail), then answer is Yes iff f(tail) >= end.
# f is non-increasing. We can compute f for all tail values from 1 to N-1.
# This is O(N) precomputation and O(1) per query!
#
# Wait, let me double-check. The constraint was:
# j in [tail, N-end], Z[j] >= end, ZR[N-j] >= tail.
#
# j >= tail: included in bj = min(j, ZR[N-j]) >= tail, since bj >= tail implies j >= tail.
# j <= N-end: included in aj = min(Z[j], N-j) >= end, since aj >= end implies N-j >= end, i.e., j <= N-end.
# Z[j] >= end: included in aj >= end since aj = min(Z[j], N-j).
# ZR[N-j] >= tail: included in bj >= tail since bj = min(j, ZR[N-j]).
#
# Yes! All four conditions are captured by bj >= tail and aj >= end.
# So f(tail) = max over {j : bj >= tail} of aj.
# Answer Yes iff f(tail) >= end.
# Precompute f:
# f[t] = max(aj for j in 1..N-1 if min(j, ZR[N-j]) >= t)
# for t = 1, 2, ..., N-1.
# To compute: iterate over all j from 1 to N-1, for each j, it contributes to all t <= bj.
# f[t] = max of aj over all j with bj >= t.
# Compute: create array f of size N+1, init 0.
# For each j, f[1..bj] could be updated with aj. But that's O(N) per j in worst case.
# Better: f[bj] = max(f[bj], aj) for each j, then sweep from right to left:
# f[t] = max(f[t], f[t+1]).
# Wait, f[t] = max over {j: bj >= t} of aj = max over {j: bj = t} of aj, union with {j: bj > t}.
# So f[t] = max(f[t+1], max(aj for j with bj = t)).
# So: initialize g[t] = max(aj for j with bj = t), then f[t] = max(g[t], f[t+1]).
max_b = N # bj can be at most N-1 since j <= N-1 and ZR[N-j] <= N.
g = [0] * (N + 1)
for j in range(1, N):
bj = min(j, ZR[N - j])
aj = min(Z[j], N - j)
if bj >= 1 and aj >= 1:
if aj > g[bj]:
g[bj] = aj
f = [0] * (N + 2)
for t in range(N, 0, -1):
f[t] = max(g[t] if t <= N else 0, f[t + 1] if t + 1 <= N + 1 else 0)
out = []
for i in range(Q):
L = int(input_data[idx]); idx += 1
R = int(input_data[idx]); idx += 1
length = R - L + 1
if length > N:
out.append("No")
continue
start = (L - 1) % N # 0-indexed start in S
# T = (S+S)[start : start+length]
if start + length <= N:
# T is entirely within S, so it's trivially a substring of S
out.append("Yes")
continue
# Wrapping case
tail = N - start # length of suffix part: S[start:N]
end = length - tail # length of prefix part: S[0:end]
# Need f[tail] >= end
if tail <= N and f[tail] >= end:
out.append("Yes")
else:
out.append("No")
sys.stdout.write('\n'.join(out) + '\n')
solve()
この解説は claude4.6opus-thinking によって生成されました。
投稿日時:
最終更新: