Overview

This problem asks, for each query, how many times a modified pattern — obtained by reversing a specified interval of a base pattern \(P\) — appears in a specified sample string. Using rolling hashes, we precompute and store substring hashes of each sample in a dictionary during preprocessing, then compute the hash of the modified pattern in \(O(1)\) per query to determine the number of occurrences.

Analysis

Problems with the Naive Approach

If we naively construct the modified pattern \(P'\) for each query and linearly search through the sample string, it costs \(O(|S_i| \cdot |P|)\) per query, resulting in a maximum of \(O(Q \cdot |S_i| \cdot |P|) \approx 10^{16}\) for \(Q\) queries, which causes TLE.

Key Observations

1. Sample-side information is fixed: For each sample, there are at most \(|S_i| - |P| + 1\) substrings of length \(|P|\), so we can precompute all their hash values.

2. The modified pattern’s hash can be computed in \(O(1)\): Since \(P' = P[0..l\text{-}2] + \text{reverse}(P[l\text{-}1..r\text{-}1]) + P[r..|P|\text{-}1]\) consists of 3 parts, by precomputing prefix hashes of \(P\) and reversed \(P\), we can obtain and combine each part’s hash in \(O(1)\).

3. Hash of the reversed portion: If we let \(P_{\text{rev}}\) be the reversal of \(P\), then \(\text{reverse}(P[l\text{-}1..r\text{-}1])\) corresponds to \(P_{\text{rev}}[|P|\text{-}r..|P|\text{-}l]\).

Algorithm

Preprocessing

1. Power array computation: Compute \(\text{pow}[i] = \text{BASE}^i \mod \text{MOD}\) up to \(|P|\).
2. Hash dictionary for each sample: Compute prefix hashes of sample \(S_i\), and store the hash values of all substrings of length \(|P|\) as keys with their occurrence counts in a dictionary.
3. Pattern prefix hashes: Compute prefix hash arrays for \(P\) and \(P_{\text{rev}}\) (the reversal of \(P\)).

Query Processing

For query \((i, l, r)\), compute the hash of the modified pattern \(P'\) as follows:

\[h(P') = h(\text{left}) \cdot \text{BASE}^{|P|-(l-1)} + h(\text{mid}) \cdot \text{BASE}^{|P|-r} + h(\text{right})\]

• \(h(\text{left}) = \) hash of \(P[0..l\text{-}2]\) from the prefix hash of \(P\)
• \(h(\text{mid}) = \) hash of \(P_{\text{rev}}[|P|\text{-}r..|P|\text{-}l]\) from the prefix hash of \(P_{\text{rev}}\)
• \(h(\text{right}) = \) hash of \(P[r..|P|\text{-}1]\) from the prefix hash of \(P\)

Using the computed hash value as a key, retrieve the occurrence count from the dictionary of sample \(S_i\).

Hash Collision Countermeasures

We use double hashing with two different MODs (\(2^{61}-1\) and \(2^{31}-1\)) to minimize the probability of collisions.

Complexity

• Time complexity: \(O\left(\sum_{i=1}^{N}|S_i| + |P| + Q\right)\)
  • Preprocessing: \(O(\sum |S_i|)\) for sample hash computation, \(O(|P|)\) for pattern prefix hashes
  • Each query: \(O(1)\) (hash computation + dictionary lookup)
• Space complexity: \(O\left(\sum_{i=1}^{N}|S_i| + |P|\right)\)

Implementation Notes

• Choice of MOD: \(2^{61}-1\) is a Mersenne prime, enabling fast mod operations and low collision probability.

• Index conversion for the reversed portion: The reversal of \(P[l\text{-}1..r\text{-}1]\) corresponds to positions \(|P|-r\) through \(|P|-l\) on \(P_{\text{rev}}\) (0-indexed).

• Hash composition: The hash of the concatenation of 3 parts is obtained by multiplying each part’s hash by the appropriate power and summing them.

• Handling negative mod: Subtraction may produce negative values; in Python, the correct modular result is obtained automatically, but care is needed in other languages.

  Source Code

import sys
from functools import lru_cache

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    
    N, Q = int(tokens[idx]), int(tokens[idx+1])
    idx += 2
    
    P = tokens[idx]
    idx += 1
    
    S = []
    for i in range(N):
        S.append(tokens[idx])
        idx += 1
    
    lenP = len(P)
    
    # Precompute rolling hashes for each sample string
    # We'll use double hashing to avoid collisions
    
    MOD1 = (1 << 61) - 1
    MOD2 = (1 << 31) - 1
    BASE1 = 131
    BASE2 = 137
    
    # Map characters to numbers
    char_map = {'H': 1, 'M': 2, 'L': 3}
    
    # For each sample, precompute hash of every substring of length lenP
    # Store in a dict: sample_index -> set/dict of hashes -> count
    
    # Precompute power arrays
    pow1 = [1] * (lenP + 1)
    pow2 = [1] * (lenP + 1)
    for i in range(1, lenP + 1):
        pow1[i] = (pow1[i-1] * BASE1) % MOD1
        pow2[i] = (pow2[i-1] * BASE2) % MOD2
    
    # For each sample, compute prefix hashes and store substring hashes
    sample_hash_counts = []
    for si in range(N):
        s = S[si]
        ls = len(s)
        hash_count = {}
        if ls >= lenP:
            # Compute prefix hashes
            ph1 = [0] * (ls + 1)
            ph2 = [0] * (ls + 1)
            for k in range(ls):
                c = char_map[s[k]]
                ph1[k+1] = (ph1[k] * BASE1 + c) % MOD1
                ph2[k+1] = (ph2[k] * BASE2 + c) % MOD2
            
            for a in range(ls - lenP + 1):
                h1 = (ph1[a + lenP] - ph1[a] * pow1[lenP]) % MOD1
                h2 = (ph2[a + lenP] - ph2[a] * pow2[lenP]) % MOD2
                key = (h1, h2)
                hash_count[key] = hash_count.get(key, 0) + 1
        
        sample_hash_counts.append(hash_count)
    
    # For pattern P, precompute prefix and suffix hashes
    P_vals = [char_map[c] for c in P]
    
    # prefix_hash1[k] = hash of P[0..k-1]
    P_prefix1 = [0] * (lenP + 1)
    P_prefix2 = [0] * (lenP + 1)
    for k in range(lenP):
        P_prefix1[k+1] = (P_prefix1[k] * BASE1 + P_vals[k]) % MOD1
        P_prefix2[k+1] = (P_prefix2[k] * BASE2 + P_vals[k]) % MOD2
    
    # suffix hash: hash of P[k..lenP-1] read forwards
    # We need hash of reversed segment P[l-1..r-1]
    # Reversed segment: P[r-1], P[r-2], ..., P[l-1]
    
    # Precompute prefix hashes of reversed P
    P_rev = P_vals[::-1]
    P_rev_prefix1 = [0] * (lenP + 1)
    P_rev_prefix2 = [0] * (lenP + 1)
    for k in range(lenP):
        P_rev_prefix1[k+1] = (P_rev_prefix1[k] * BASE1 + P_rev[k]) % MOD1
        P_rev_prefix2[k+1] = (P_rev_prefix2[k] * BASE2 + P_rev[k]) % MOD2
    
    # For query (i, l, r): P' = P[0..l-2] + reverse(P[l-1..r-1]) + P[r..lenP-1]
    # Hash of P' = hash(P[0..l-2]) * BASE^(lenP-(l-1)) + hash(reverse(P[l-1..r-1])) * BASE^(lenP-r) + hash(P[r..lenP-1])
    
    # hash(P[0..l-2]) = P_prefix[l-1]
    # hash(P[r..lenP-1]) = P_prefix[lenP] - P_prefix[r] * pow[lenP-r]
    # reverse(P[l-1..r-1]) in reversed P is at index (lenP-r) to (lenP-l)
    # hash of that = P_rev_prefix[lenP-l+1] - P_rev_prefix[lenP-r] * pow[r-l+1]
    
    out = []
    for _ in range(Q):
        ij = int(tokens[idx]) - 1
        lj = int(tokens[idx+1])
        rj = int(tokens[idx+2])
        idx += 3
        
        seg_len = rj - lj + 1
        after_len = lenP - rj
        
        # Hash1
        h1_left = P_prefix1[lj - 1]
        rev_start = lenP - rj
        rev_end = lenP - lj + 1
        h1_mid = (P_rev_prefix1[rev_end] - P_rev_prefix1[rev_start] * pow1[seg_len]) % MOD1
        h1_right = (P_prefix1[lenP] - P_prefix1[rj] * pow1[after_len]) % MOD1
        
        h1 = (h1_left * pow1[seg_len + after_len] + h1_mid * pow1[after_len] + h1_right) % MOD1
        
        # Hash2
        h2_left = P_prefix2[lj - 1]
        h2_mid = (P_rev_prefix2[rev_end] - P_rev_prefix2[rev_start] * pow2[seg_len]) % MOD2
        h2_right = (P_prefix2[lenP] - P_prefix2[rj] * pow2[after_len]) % MOD2
        
        h2 = (h2_left * pow2[seg_len + after_len] + h2_mid * pow2[after_len] + h2_right) % MOD2
        
        key = (h1 % MOD1, h2 % MOD2)
        out.append(str(sample_hash_counts[ij].get(key, 0)))
    
    sys.stdout.write('\n'.join(out) + '\n')

solve()

---

This editorial was generated by claude4.6opus-thinking.