\(P'_j\) の長さは常に同じなので、この長さを \(M\) とすると各文字列 \(S_i\) に対し長さ \(M\) の部分文字列のハッシュをそれぞれ計算します。

各クエリでは \(P_j'\) のハッシュを計算し、一致する部分文字列の個数を求めれば良いです。

実装例(Python3)

from random import randint
import sys
from collections import defaultdict

input = sys.stdin.readline

n, q = map(int, input().split())
p1 = input().rstrip()
s = [input().rstrip() for _ in range(n)]
m = len(p1)
p2 = p1[::-1]
MOD = 2**61 - 1
mp = {"H": randint(0, MOD - 1), "M": randint(0, MOD - 1), "L": randint(0, MOD - 1)}
B = 37
B_inv = pow(B, MOD - 2, MOD)
INF = 5 * 10**5
b = [1] * (INF + 1)
b_inv = [1] * (INF + 1)
for i in range(INF):
    b[i + 1] = b[i] * B % MOD
    b_inv[i + 1] = b_inv[i] * B_inv % MOD
h1 = [0] * (m + 1)
h2 = [0] * (m + 1)
for i in range(m):
    h1[i + 1] = (h1[i] + mp[p1[i]] * b[i]) % MOD
    h2[i + 1] = (h2[i] + mp[p2[i]] * b[i]) % MOD
ans = [defaultdict(int) for _ in range(n)]
for idx in range(n):
    h = [0] * (len(s[idx]) + 1)
    for i in range(len(s[idx])):
        h[i + 1] = (h[i] + mp[s[idx][i]] * b[i]) % MOD
    for i in range(len(s[idx]) - m + 1):
        ans[idx][(h[i + m] - h[i]) * b_inv[i] % MOD] += 1
for _ in range(q):
    i, l, r = map(int, input().split())
    i -= 1
    l -= 1
    res = (h1[l] - h1[0]) + (h2[m - l] - h2[m - r]) * b_inv[m - r] * b[l] + (h1[m] - h1[r])
    print(ans[i][res % MOD])