我们记 count(h) 为字符串 h 的所有子串中，出现在集合 S 里的子串数量。对于每个询问，我们需要计算 count(h[l_i, r_i])。令 pref[i] = count(t[0:i))，即 t 的长度为 i 的前缀中，出现在 S 中的子串数量。令 suf[i] = count(t[i:|t|))，即从位置 i 开始的后缀在 S 中出现的子串数量。
可以发现，pref[r] + suf[l] - count(t) 等于 count(t[l, r])，再减去那些属于 S 的子串，这些子串在 t 中的起点早于 l，终点晚于 r。如果不存在这种“跨界”子串，那么答案就很容易求出，所有需要的 pref[l] 和 suf[r] 都可以通过 Aho-Corasick 算法计算得到。
如果存在上述“跨界”子串，则对于询问 t[l, r]，我们需要找到这样一个 S 中的子串 s_i，它在 t 中的出现起点早于 l，终点晚于 r。在所有满足条件的 s_i 中，选择右端点最靠左的那个。设其为 s_i。注意，t[l, r] 是 s_i 的一个子串，记作 s_i[l', r']。同时，s_i 中不存在起点早于 l'、终点晚于 r'且属于 S 的子串（否则 t[l, r] 会被更靠右的 S 中子串覆盖）。因此，我们可以对 s_i 应用前缀和后缀的原理，递归求解。
为了在询问 t[l, r] 时找到合适的 s_i，我们可以用扫描线遍历 t。利用 Aho-Corasick 算法，对于每个位置 i，找到以 i 结尾的、属于 S 的最长子串（记为 s_j）。同时，在一个堆或 set 结构中维护所有右端点不超过 i 的询问的起点。对于每个起点晚于 s_j 起点的询问，s_j 都是合法的覆盖子串。所有这些询问随后从堆中移除。