概要

無限に繰り返される文字列から切り出された部分文字列が、元の文字列の部分文字列として存在するかを判定する問題です。文字列の周期性を利用した条件の言い換えと、Z algorithm・オフラインクエリ処理（平面走査法 / スイープライン）を組み合わせることで効率的に解くことができます。

考察

1. 自明なケースの判定

まず、切り出す文字列 \(T_i\) の長さ \(L = R_i - L_i + 1\) が \(N\) より大きい場合、長さ \(N\) の \(S\) の部分文字列になることは絶対にないため、答えは No です。 次に、\(T_i\) の開始位置は \(S\) の先頭から \(p = (L_i - 1) \bmod N\) 文字目（0-indexed）に相当します。もし \(p + L \leq N\) であれば、\(T_i\) は \(S\) の途中で途切れることなく完全に含まれるため、無条件で Yes となります。

2. 境界をまたぐケースの言い換え

問題となるのは \(p + L > N\) の場合です。このとき、\(T_i\) は \(S\) の末尾 \(X = N - p\) 文字と、先頭 \(Y = L - X\) 文字を連結した文字列になります。 この \(T_i\) が \(S\) の部分文字列として出現するということは、\(S\) のある分割位置 \(k\) （\(1 \leq k < N\)）が存在し、以下の2つの条件を同時に満たすことと同値です。 - \(S\) の \(k\) の直前の \(X\) 文字が、\(S\) の末尾 \(X\) 文字と一致する - \(S\) の \(k\) から始まる \(Y\) 文字が、\(S\) の先頭 \(Y\) 文字と一致する

3. Z algorithm の活用

上記の条件は、以下のように言い換えられます。 - 後者の条件：\(S\) と \(S[k \dots N-1]\) の最長共通接頭辞（LCP）の長さが \(Y\) 以上である。 - 前者の条件：\(S\) と \(S[0 \dots k-1]\) の最長共通接尾辞（LCS）の長さが \(X\) 以上である。

LCP は Z algorithm を用いることで、\(O(N)\) で各 \(k\) について計算できます。LCS についても、\(S\) を反転させた文字列に対して Z algorithm を適用することで同様に計算可能です。 これにより、各分割位置 \(k\) について「LCSの長さ \(x_k\)」と「LCPの長さ \(y_k\)」のペア \((x_k, y_k)\) が得られます。

4. 2次元クエリへの帰着

各クエリは「条件 \(x_k \geq X\) かつ \(y_k \geq Y\) を満たす点 \((x_k, y_k)\) が存在するか？」という2次元の直交領域クエリに帰着されます。これは、点とクエリを事前にソートして処理するオフラインクエリ処理（スイープライン）で高速に解くことができます。

アルゴリズム

1. Z algorithm の前計算:
   • 文字列 \(S\) に対して Z algorithm を適用し、配列 Z を求めます。
   • 文字列 \(S\) を反転させたものに対して Z algorithm を適用し、配列 Z_R を求めます。
2. 点の生成:
   • 各分割位置 \(k\) (\(1 \leq k < N\)) について、点 \((x_k, y_k) = (\text{Z\_R}[N - k], \text{Z}[k])\) を作成します。
   • 作成した点群を \(x_k\) の降順（大きい順）にソートします。
3. クエリの準備:
   • 各質問について、自明な Yes / No を判定します。
   • 境界をまたぐ場合は、必要な長さ \((X, Y)\) を計算し、元の質問番号とともにクエリとして保存します。
   • クエリ群を \(X\) の降順にソートします。
4. スイープラインによる判定:
   • クエリを順番に処理します。現在のクエリの \(X\) 以上の \(x_k\) を持つ点について、\(y_k\) の最大値 max_y を更新していきます。
   • max_y \(\geq Y\) であれば、そのクエリの答えは Yes、そうでなければ No となります。
5. 出力:
   • 元の質問順に答えを出力します。

計算量

• 時間計算量: \(O(N \log N + Q \log Q)\)
  • Z algorithm の計算は \(O(N)\) です。
  • 点のソートに \(O(N \log N)\)、クエリのソートに \(O(Q \log Q)\) かかります。
  • スイープラインの処理自体は \(O(N + Q)\) です。
• 空間計算量: \(O(N + Q)\)
  • Z配列、点群のリスト、クエリのリスト、答えを格納する配列を保持するためのメモリが必要です。

実装のポイント

• 文字列処理の高速化: Pythonで文字列の比較や処理を行う際、S.encode('ascii') を使ってバイト列（bytes）に変換してから Z algorithm に渡すことで、処理速度を向上させることができます。

• 元のインデックスの保持: クエリを \(X\) の降順にソートするため、処理順序が元の質問順と異なります。クエリのタプルに元のインデックス i を含めておき、答えを配列 ans の正しい位置に格納するように実装します。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    Q = int(data[1])
    S = data[2]
    
    def z_algorithm(s):
        n = len(s)
        z = [0] * n
        if n == 0:
            return z
        z[0] = n
        l, r = 0, 0
        for i in range(1, n):
            if i <= r:
                z[i] = min(r - i + 1, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] - 1 > r:
                l = i
                r = i + z[i] - 1
        return z

    S_bytes = S.encode('ascii')
    Z = z_algorithm(S_bytes)
    Z_R = z_algorithm(S_bytes[::-1])
    
    points = [(Z_R[N - k], Z[k]) for k in range(1, N)]
    points.sort(key=lambda p: p[0], reverse=True)
    
    queries = []
    ans = ['No'] * Q
    
    idx = 3
    for i in range(Q):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        
        length = R - L + 1
        if length > N:
            continue
            
        p = (L - 1) % N
        if p + length <= N:
            ans[i] = 'Yes'
        else:
            X = N - p
            Y = length - X
            queries.append((X, Y, i))
            
    queries.sort(key=lambda q: q[0], reverse=True)
    
    point_idx = 0
    max_y = -1
    
    for X, Y, q_idx in queries:
        while point_idx < len(points) and points[point_idx][0] >= X:
            if points[point_idx][1] > max_y:
                max_y = points[point_idx][1]
            point_idx += 1
        if max_y >= Y:
            ans[q_idx] = 'Yes'
            
    print('\n'.join(ans))

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.1-pro-thinking によって生成されました。