Overview

This problem asks us to determine, for multiple queries, how many times a modified pattern \(P'_j\) — obtained by reversing a portion of a given base pattern \(P\) — appears in a specified string \(S_{i_j}\).

Since the string lengths and number of queries can be very large, instead of naively constructing the modified pattern and searching for each query, we combine Rolling Hash and binary search to process each query in \(O(\log |S_{i_j}|)\) time.

Analysis

Naive Approach and Its Limitations

For each query \((i_j, l_j, r_j)\), if we actually reverse the interval \([l_j, r_j]\) of \(P\) to create \(P'_j\) and search for \(P'_j\) in \(S_{i_j}\) using KMP or rolling hash, it takes \(O(|P| + |S_{i_j}|)\) time per query. With \(Q \le 2 \times 10^5\) queries and string lengths up to \(5 \times 10^5\), the worst-case total complexity becomes \(O(Q (|P| + |S_i|))\), which exceeds the time limit (TLE).

Key Idea for Optimization

Although the target string \(S_{i_j}\) and modified pattern \(P'_j\) change for each query, we focus on the following two observations:

1. Precomputation of substring hashes for \(S_i\) For each \(S_i\), we precompute the hash values of all contiguous substrings of length \(|P|\), and store them in sorted order. If we can quickly compute the hash value \(HP'_j\) of the modified pattern \(P'_j\), we can count its occurrences efficiently by performing binary search (e.g., std::equal_range) on the sorted hash value array.

2. Fast composition of the hash value for \(P'_j\) The modified pattern \(P'_j\) can be expressed as three parts of the original base pattern \(P\) (considering 0-indexed, let \(l' = l_j - 1, r' = r_j - 1\)):

   • Left (not reversed): \(P[0 \dots l'-1]\)
   • Middle (reversed): Reversal of \(P[l' \dots r']\)
   • Right (not reversed): \(P[r'+1 \dots |P|-1]\)

If we can obtain the hash value of each of these three parts in \(O(1)\), then we can compute the combined overall hash value \(HP'_j\) in \(O(1)\) as well.

Algorithm

1. Rolling Hash Setup

To prevent hash collisions (the phenomenon where different strings have the same hash value), we use a rolling hash with a very large prime modulus \(MOD = 2^{61}-1\) and a randomly chosen base \(B\).

2. Precomputation of Tables

• Build prefix hash arrays for the base pattern \(P\) and its reversed string \(P_{rev}\). This allows us to retrieve the hash value of any interval in \(O(1)\).
• For each \(S_i\), compute the hash values of all contiguous substrings of length \(|P|\) using a sliding window, store them in an array V[i], and sort in ascending order.

3. Query Processing (Hash Composition)

For each query, we compose the hash value \(HP'_j\) of the modified pattern \(P'_j\) as follows:

• Left hash \(H_A\): Hash value of \(P\)’s interval \([0, l'-1]\). Obtained in \(O(1)\) from \(P\)’s prefix hash.
• Middle hash \(H_B\): Hash value of the reversal of \(P\)’s interval \([l', r']\). This equals the hash value of the interval \([|P|-1-r', |P|-1-l']\) in the reversed string \(P_{rev}\), so it can be obtained in \(O(1)\) from \(P_{rev}\)’s prefix hash.
• Right hash \(H_C\): Hash value of \(P\)’s interval \([r'+1, |P|-1]\). Obtained in \(O(1)\) from \(P\)’s prefix hash.

We combine these by multiplying by appropriate powers of the base \(B\) and summing: $\(HP'_j = H_A \times B^{|P| - l'} + H_B \times B^{|P| - 1 - r'} + H_C \pmod{MOD}\)$

4. Counting via Binary Search

Using the composed hash value \(HP'_j\), we perform binary search on the sorted array V[i] to find the number of elements with matching hash values in \(O(\log |S_i|)\).

---

Hash Composition with a Concrete Example

For \(P = \) HMLLM (\(|P| = 5\)), \(l_j = 2, r_j = 4\) (0-indexed: \(l' = 1, r' = 3\)):

• Original pattern: H M L L M
• Reversed pattern \(P_{rev}\): M L L M H
• Modified pattern \(P'_j\): H L L M M

1. Left \(A\) (H): Hash of \(P[0 \dots 0]\) \(\rightarrow H_A\)
2. Middle \(B\) (LLM): Reversal of \(P[1 \dots 3]\). This is the hash of \(P_{rev}[5-1-3 \dots 5-1-1] = P_{rev}[1 \dots 3]\) (LLM) \(\rightarrow H_B\)
3. Right \(C\) (M): Hash of \(P[4 \dots 4]\) \(\rightarrow H_C\)

We combine these to obtain the hash value of \(P'_j\).

---

Complexity

Time Complexity

• Preprocessing:

  • Hash construction for \(P\) and \(P_{rev}\): \(O(|P|)\)
  • Hash construction for all \(S_i\) and sorting of substring hashes: Sorting each \(S_i\) costs \(O(|S_i| \log |S_i|)\), so the total is \(O(\sum_{i=1}^{N} |S_i| \log |S_i|)\)

• Query processing:

  • Per query: \(O(1)\) for hash composition, \(O(\log |S_{i_j}|)\) for binary search
  • For all \(Q\) queries: \(O(Q \log (\max |S_i|))\)

• Overall time complexity: \(O(|P| + \sum_{i=1}^{N} |S_i| \log |S_i| + Q \log (\max |S_i|))\) Given the constraints \(\sum |S_i| \le 5 \times 10^5\) and \(Q \le 2 \times 10^5\), this comfortably fits within the time limit.

Space Complexity

• Hash tables for \(P, P_{rev}\), and the arrays V storing substring hashes for each \(S_i\)
• Overall space complexity: \(O(|P| + \sum_{i=1}^{N} |S_i|)\) This operates very memory-efficiently with respect to the memory limit.

Implementation Notes

• 61-bit Mersenne prime hash: By using \(2^{61}-1\) as the hash modulus (MOD), the probability of hash collisions is reduced to practically zero. Furthermore, modular arithmetic with this modulus can be accelerated using bit operations, resulting in very low constant factors.

• Randomization of base \(B\): To prevent “hack cases” that intentionally cause hash collisions, the base \(B\) is determined randomly at runtime using a random number generator.

  Source Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

using ull = unsigned long long;
const ull MOD = (1ULL << 61) - 1;

ull mul(ull a, ull b) {
    __uint128_t t = (__uint128_t)a * b;
    ull lo = (ull)t & MOD;
    ull hi = (ull)(t >> 61);
    ull res = lo + hi;
    if (res >= MOD) res -= MOD;
    return res;
}

ull add(ull a, ull b) {
    ull res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}

ull sub(ull a, ull b) {
    ull res = a + MOD - b;
    if (res >= MOD) res -= MOD;
    return res;
}

ull get_base() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<ull> dist(300, MOD - 2);
    ull b = dist(rng);
    if (b % 2 == 0) b++;
    return b;
}

vector<ull> powerB;
void init_power(ull B, int max_len) {
    powerB.resize(max_len + 1);
    powerB[0] = 1;
    for (int i = 1; i <= max_len; i++) {
        powerB[i] = mul(powerB[i - 1], B);
    }
}

vector<ull> build_hash(const string& S, ull B) {
    int n = S.length();
    vector<ull> h(n + 1, 0);
    for (int i = 0; i < n; i++) {
        h[i + 1] = add(mul(h[i], B), S[i]);
    }
    return h;
}

ull get_hash(const vector<ull>& h, int l, int r) {
    if (l > r) return 0;
    int len = r - l + 1;
    return sub(h[r + 1], mul(h[l], powerB[len]));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    string P;
    cin >> P;
    int M = P.length();

    vector<string> S(N);
    int max_len = M;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        max_len = max(max_len, (int)S[i].length());
    }

    ull B = get_base();
    init_power(B, max_len);

    vector<ull> hp = build_hash(P, B);
    string P_rev = P;
    reverse(P_rev.begin(), P_rev.end());
    vector<ull> hprev = build_hash(P_rev, B);

    vector<vector<ull>> V(N);
    for (int i = 0; i < N; i++) {
        int len = S[i].length();
        if (len >= M) {
            vector<ull> hs = build_hash(S[i], B);
            V[i].resize(len - M + 1);
            for (int a = 0; a <= len - M; a++) {
                V[i][a] = get_hash(hs, a, a + M - 1);
            }
            sort(V[i].begin(), V[i].end());
        }
    }

    for (int q = 0; q < Q; q++) {
        int i, l, r;
        cin >> i >> l >> r;
        i--;

        if (V[i].empty()) {
            cout << 0 << "\n";
            continue;
        }

        int l_prime = l - 1;
        int r_prime = r - 1;

        ull HA = get_hash(hp, 0, l_prime - 1);
        ull HB = get_hash(hprev, M - 1 - r_prime, M - 1 - l_prime);
        ull HC = get_hash(hp, r_prime + 1, M - 1);

        ull HP_prime = add(mul(HA, powerB[M - l_prime]), mul(HB, powerB[M - 1 - r_prime]));
        HP_prime = add(HP_prime, HC);

        auto range = equal_range(V[i].begin(), V[i].end(), HP_prime);
        cout << distance(range.first, range.second) << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.