Overview

This problem asks us to determine whether a substring extracted from an infinitely repeated string exists as a substring of the original string. It can be solved efficiently by combining a reformulation of conditions using the periodicity of strings, the Z algorithm, and offline query processing (sweep line method).

Analysis

1. Determining Trivial Cases

First, if the length \(L = R_i - L_i + 1\) of the extracted string \(T_i\) is greater than \(N\), it can never be a substring of \(S\) which has length \(N\), so the answer is No. Next, the starting position of \(T_i\) corresponds to position \(p = (L_i - 1) \bmod N\) from the beginning of \(S\) (0-indexed). If \(p + L \leq N\), then \(T_i\) is completely contained within \(S\) without wrapping around, so the answer is unconditionally Yes.

2. Reformulating the Boundary-Crossing Case

The interesting case is when \(p + L > N\). In this case, \(T_i\) is the concatenation of the last \(X = N - p\) characters of \(S\) and the first \(Y = L - X\) characters of \(S\). For this \(T_i\) to appear as a substring of \(S\), it is equivalent to the existence of some split position \(k\) (\(1 \leq k < N\)) in \(S\) that simultaneously satisfies the following two conditions: - The \(X\) characters immediately before position \(k\) in \(S\) match the last \(X\) characters of \(S\) - The \(Y\) characters starting from position \(k\) in \(S\) match the first \(Y\) characters of \(S\)

3. Utilizing the Z Algorithm

The above conditions can be reformulated as follows: - Latter condition: The length of the longest common prefix (LCP) between \(S\) and \(S[k \dots N-1]\) is at least \(Y\). - Former condition: The length of the longest common suffix (LCS) between \(S\) and \(S[0 \dots k-1]\) is at least \(X\).

The LCP can be computed for each \(k\) in \(O(N)\) using the Z algorithm. The LCS can similarly be computed by applying the Z algorithm to the reversed string of \(S\). This gives us, for each split position \(k\), a pair \((x_k, y_k)\) of “LCS length \(x_k\)” and “LCP length \(y_k\)”.

4. Reduction to 2D Queries

Each query is reduced to a 2D orthogonal range query: “Does there exist a point \((x_k, y_k)\) satisfying \(x_k \geq X\) and \(y_k \geq Y\)?” This can be solved efficiently using offline query processing (sweep line) by pre-sorting points and queries.

Algorithm

1. Precomputation with Z algorithm:
   • Apply the Z algorithm to string \(S\) to obtain array Z.
   • Apply the Z algorithm to the reversed string of \(S\) to obtain array Z_R.
2. Point generation:
   • For each split position \(k\) (\(1 \leq k < N\)), create a point \((x_k, y_k) = (\text{Z\_R}[N - k], \text{Z}[k])\).
   • Sort the generated points in descending order of \(x_k\).
3. Query preparation:
   • For each question, determine trivial Yes / No cases.
   • For boundary-crossing cases, compute the required lengths \((X, Y)\) and save them as queries along with the original question index.
   • Sort the queries in descending order of \(X\).
4. Sweep line determination:
   • Process queries in order. For points with \(x_k\) greater than or equal to the current query’s \(X\), update the maximum value max_y of \(y_k\).
   • If max_y \(\geq Y\), the answer for that query is Yes; otherwise it is No.
5. Output:
   • Output answers in the original question order.

Complexity

• Time complexity: \(O(N \log N + Q \log Q)\)
  • Z algorithm computation is \(O(N)\).
  • Sorting points takes \(O(N \log N)\), and sorting queries takes \(O(Q \log Q)\).
  • The sweep line processing itself is \(O(N + Q)\).
• Space complexity: \(O(N + Q)\)
  • Memory is needed to store the Z arrays, the list of points, the list of queries, and the answer array.

Implementation Notes

• Speeding up string processing: When performing string comparison and processing in Python, converting to a byte string (bytes) using S.encode('ascii') before passing it to the Z algorithm can improve processing speed.

• Preserving original indices: Since queries are sorted in descending order of \(X\), the processing order differs from the original question order. Include the original index i in the query tuple and implement it so that answers are stored at the correct position in the array ans.

  Source Code

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()

This editorial was generated by gemini-3.1-pro-thinking.