概要

無限に繰り返される文字列 \(S^{\infty}\) の区間 \([L_i, R_i]\) で得られる文字列 \(T_i\) が、元の \(S\) の部分文字列として現れるかを \(Q\) 回判定します。各クエリを \(O(1)\) で処理するために、\(S\) の Suffix Automaton（SAM）を作り、\(S+S\) 上で前計算します。

考察

重要な観察 1：見るべきは \(S+S\) で十分

\(T_i\) の長さを \(m = R_i - L_i + 1\) とすると、

• \(m > N\) なら、長さ \(N\) の \(S\) の部分文字列になれないので必ず No。
• \(m \le N\) のとき、\(T_i\) は \(S^{\infty}\) のある位置から始まりますが、その開始位置は \(S\) 内の位置 [ a = (L_i - 1)\bmod N \quad (0\text{-indexed}) ] で決まります。

長さ \(m \le N\) なら、\(T_i\) は高々 2 回分の連結に収まるため、必ず [ T_i = (S+S)[a \dots a+m-1] ] になります。つまり 各クエリは「\(S+S\) のある部分文字列が \(S\) に出現するか？」 という問題に変換できます。

重要な観察 2：素朴は間に合わない

各クエリごとに \(T_i\) を実際に取り出して、\(S\) 内を検索（例えば KMP や find）すると、最悪で - 取り出しに \(O(m)\) - 検索に \(O(N+m)\) がかかり、\(Q\) が最大 \(2\times 10^5\) なので到底間に合いません。

そこで、「\(S\) に現れる部分文字列かどうか」を高速に判定できるデータ構造（SAM）を使い、さらに \(S+S\) 側もまとめて走査して クエリを \(O(1)\) に落とします。

アルゴリズム

1. Suffix Automaton（SAM）を構築

SAM は、文字列 \(S\) の すべての部分文字列 を受理するオートマトンです。
\(S\) を左から 1 文字ずつ追加していけば、\(O(N)\) で構築できます。

2. \(T = S+S\) を SAM 上で走査し、dp を作る

\(T\) の各位置 \(i\)（\(0\)-indexed）について

• dp[i] = 「\(T\) の位置 \(i\) で終わる部分文字列のうち、\(S\) に出現するものの最大長」

を計算します。

SAM 上で現在状態 v と一致長 l を持ちながら \(T\) を読むとき、次の遷移が無ければ suffix link を辿って「一致するまで短くする」という操作をします。これは典型的な SAM のマッチングで、全体で \(O(|T|)=O(N)\) で動きます。

こうして dp ができると、任意の区間 \([a, a+m-1]\)（終端を \(e=a+m-1\) とする）が \(S\) に出現するかは

• 「長さ \(m\) の部分文字列が \(T\) の位置 \(e\) で終わっていて、かつそれが \(S\) に出現する」
• これは dp[e] >= m と同値

で判定できます。

3. クエリ処理（\(O(1)\)）

各クエリで 1. \(m = R-L+1\) が \(N\) を超えたら No 2. \(a = (L-1)\bmod N\), \(e=a+m-1\) 3. dp[e] >= m なら Yes、そうでなければ No

とします。

計算量

• 時間計算量:
  
  • SAM 構築 \(O(N)\)
    
  • \(T=S+S\) の走査 \(O(N)\)
    
  • 各クエリ \(O(1)\) を \(Q\) 回
    よって全体で \(O(N+Q)\)
• 空間計算量:
  SAM の状態数は最大 \(2N-1\) 程度なので、遷移（26 文字固定）など含めて \(O(N)\)

実装のポイント

• \(L_i, R_i\) は最大 \(10^{18}\) なので、開始位置は必ず \((L_i-1)\bmod N\) で求めます（Python の int なら安全）。

• dp の添字は \(0\)-indexed で扱い、終端 \(e=a+m-1\) を間違えないようにします。

• Python では速度とメモリのために

  • 文字列を bytes で持つ（b - 97 で 0〜25 に変換）

  • SAM の遷移を array('i') の 1 次元配列（state*26 + c）で持つ
    といった工夫をしています。

    ソースコード

import sys
from array import array

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    Q = int(data[1])
    S = data[2]  # bytes

    max_states = 2 * N + 5
    nxt = array('i', [-1]) * (max_states * 26)
    link = array('i', [-1]) * max_states
    length = array('i', [0]) * max_states

    size = 1
    last = 0
    link[0] = -1
    length[0] = 0

    # Build SAM for S
    for b in S:
        c = b - 97
        cur = size
        size += 1
        length[cur] = length[last] + 1

        p = last
        pc = p * 26 + c
        while p != -1 and nxt[pc] == -1:
            nxt[pc] = cur
            p = link[p]
            if p != -1:
                pc = p * 26 + c

        if p == -1:
            link[cur] = 0
        else:
            q = nxt[p * 26 + c]
            if length[p] + 1 == length[q]:
                link[cur] = q
            else:
                clone = size
                size += 1
                src = q * 26
                dst = clone * 26
                for k in range(26):
                    nxt[dst + k] = nxt[src + k]
                length[clone] = length[p] + 1
                link[clone] = link[q]

                while p != -1 and nxt[p * 26 + c] == q:
                    nxt[p * 26 + c] = clone
                    p = link[p]

                link[q] = clone
                link[cur] = clone

        last = cur

    # Scan T = S+S and compute dp[i] = longest match ending at i that occurs in S
    T = S + S
    Tlen = 2 * N
    dp = array('i', [0]) * Tlen

    v = 0
    l = 0
    for i in range(Tlen):
        c = T[i] - 97
        idx = v * 26 + c
        while v and nxt[idx] == -1:
            v = link[v]
            l = length[v]
            idx = v * 26 + c
        to = nxt[idx]
        if to != -1:
            v = to
            l += 1
        else:
            v = 0
            l = 0
        dp[i] = l

    it = iter(data[3:])
    out_lines = []
    for _ in range(Q):
        L = int(next(it))
        R = int(next(it))
        m = R - L + 1
        if m > N:
            out_lines.append("No")
            continue
        a = (L - 1) % N
        e = a + m - 1
        out_lines.append("Yes" if dp[e] >= m else "No")

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。