区间显然不好处理，考虑转化成前缀和后缀。
设 \(f'_i\) 为 \(T[1 : i]\) 的单词出现次数，\(f_i\) 为 \(f'_i\) 的前缀和，\(g_i\) 为 \(T[1 : i]\) 后缀最长的单词编号。都可以通过建 \(s_i\) 正串的 ACAM 预处理。
对于询问 \((l, r)\)，一个简单的想法是直接回答 \(f_r - f_{l - 1}\)。但是我们多算了左端点在 \(l\) 之前的串。
考虑找到最大的 \(p\) 使得 \(p - |s_{g_p}| + 1 \le l\)，这样右端点在 \([p + 1, r]\) 的答案就是 \(f_r - f_p\)。再建反串 ACAM 预处理出 \(h_{i, j}\) 表示 \(s_i\) 长度为 \(j\) 的后缀有多少个串，就可以回答右端点在 \([l, p]\) 的答案。
找 \(p\) 可以线段树上二分。
code
// Problem: G. A task for substrings
// Contest: Codeforces - Codeforces Round 857 (Div. 1)
// URL: https://codeforces.com/contest/1801/problem/G
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100, maxm = 5000100;
int n, m, len, g[maxm];
ll f[maxm];
char t[maxm];
string s[maxn], rs[maxn];
vector<ll> h[maxn];
struct AC {
int ch[maxn][26], fail[maxn], ntot, ed[maxn], id[maxn];
inline void insert(string s, int k) {
int p = 0;
for (char c : s) {
if (!ch[p][c - 'a']) {
ch[p][c - 'a'] = ++ntot;
}
p = ch[p][c - 'a'];
}
ed[p] = 1;
id[p] = k;
}
inline void build() {
queue<int> q;
for (int i = 0; i < 26; ++i) {
if (ch[0][i]) {
q.push(ch[0][i]);
}
}
while (q.size()) {
int u = q.front();
q.pop();
ed[u] += ed[fail[u]];
if (!id[u]) {
id[u] = id[fail[u]];
}
for (int i = 0; i < 26; ++i) {
if (ch[u][i]) {
fail[ch[u][i]] = ch[fail[u]][i];
q.push(ch[u][i]);
} else {
ch[u][i] = ch[fail[u]][i];
}
}
}
}
} ac, ca;
namespace SGT {
int mn[maxm << 2];
inline void pushup(int x) {
mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}
void build(int rt, int l, int r) {
if (l == r) {
mn[rt] = l - (int)s[g[l]].size() + 1;
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
int findr(int rt, int l, int r, int x) {
if (mn[rt] > x) {
return -1;
}
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
return (mn[rt << 1 | 1] <= x) ? findr(rt << 1 | 1, mid + 1, r, x) : findr(rt << 1, l, mid, x);
}
int findr(int rt, int l, int r, int ql, int qr, int x) {
if (mn[rt] > x) {
return -1;
}
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (qr > mid) {
int t = findr(rt << 1 | 1, mid + 1, r, ql, qr, x);
if (t != -1) {
return t;
}
}
if (ql <= mid) {
int t = findr(rt << 1, l, mid, ql, qr, x);
if (t != -1) {
return t;
}
}
return -1;
}
}
void solve() {
cin >> n >> m >> (t + 1);
len = strlen(t + 1);
for (int i = 1; i <= n; ++i) {
cin >> s[i];
rs[i] = s[i];
reverse(rs[i].begin(), rs[i].end());
ac.insert(s[i], i);
ca.insert(rs[i], i);
}
ac.build();
ca.build();
int p = 0;
for (int i = 1; i <= len; ++i) {
p = ac.ch[p][t[i] - 'a'];
g[i] = ac.id[p];
f[i] = f[i - 1] + ac.ed[p];
}
for (int i = 1; i <= n; ++i) {
h[i].resize(s[i].size());
int p = 0;
for (int j = 0; j < (int)s[i].size(); ++j) {
if (j) {
h[i][j] = h[i][j - 1];
}
p = ca.ch[p][rs[i][j] - 'a'];
h[i][j] += ca.ed[p];
}
}
SGT::build(1, 1, len);
while (m--) {
int l, r;
cin >> l >> r;
int p = SGT::findr(1, 1, len, l, r, l);
if (p == -1) {
printf("%lld ", f[r] - f[l - 1]);
} else {
printf("%lld ", f[r] - f[p] + h[g[p]][p - l]);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}