直接做没什么思路，那就考虑根号算法
令 $\mathrm{s[k]}$ 的长度为 $\mathrm{len}$.
如果 $\mathrm{len}$ 的长度大于根号 $\mathrm{n}$, 则这样的 $\mathrm{s[k]}$ 很少.
可以直接枚举长度大于根号的串，然后和其他所有串去匹配.
具体方法就是建出所有串的 AC 自动机，然后标记上长串的所有节点.
枚举其他所有串，每次做一个子树查询（DFS序上的区间查询）
由于更新次数为 $O(n)$, 直接做一个前缀和，不用数据结构.
对于 $\mathrm{s[k]}$ 串很短的情况，直接暴力枚举左端点，然后向右移动右端点.
建一个 $\mathrm{trie}$ 树然后二分位置就完事了.
块的大小取 300 左右差不多能过.
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
#define B 350
#define N 100009
#define pb push_back
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
struct BIT {
int C[N];
void upd(int x, int v) {
C[x]+=v;
}
void upd() {
for(int i=1;i<100009;++i) C[i] += C[i-1];
}
int query(int x) {
return C[x];
}
void clr() {
for(int i=0;i<100009;++i) C[i]=0;
}
int Q(int l,int r) {
if(l>r) return 0;
return query(r)-query(l-1);
}
}T;
char str[N];
queue<int>que;
vector<int>ss[N],G[N],ind[N];
int n,Q,cnt,tot,scc, nod,re[N];
int id[N],fin[N],ch[N][26],fail[N],st[N],ed[N],c2[N][26];
ll f[250+2][100009];
void dfs(int x) {
st[x]=++scc;
for(int i=0;i<G[x].size();++i) {
dfs(G[x][i]);
}
ed[x]=scc;
}
void build() {
for(int i=0;i<26;++i) {
if(ch[0][i]) {
fail[ch[0][i]]=0;
que.push(ch[0][i]);
}
}
while(!que.empty()) {
int u=que.front(); que.pop();
for(int i=0;i<26;++i) {
int q=ch[u][i];
if(!q) {
ch[u][i]=ch[fail[u]][i];
continue;
}
fail[q]=ch[fail[u]][i];
que.push(q);
}
}
for(int i=1;i<=tot;++i) {
G[fail[i]].pb(i);
}
dfs(0);
}
void calcf() {
for(int i=1;i<=cnt;++i) {
int o=re[i],rt=0;
for(int j=1;j<ss[o].size();++j) {
rt=ch[rt][ss[o][j]];
T.upd(st[rt], +1);
}
T.upd();
for(int j=1;j<=n;++j) {
int p=fin[j];
f[i][j]=(ll)T.Q(st[p], ed[p])+f[i][j-1];
}
T.clr();
}
}
int main() {
// setIO("input");
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;++i) {
scanf("%s",str+1);
int p=strlen(str+1);
ss[i].pb(0);
for(int j=1;j<=p;++j) {
ss[i].pb(str[j]-‘a‘);
}
// 大于等于 B 的编号.
if(p >= B)
re[id[i] = ++ cnt] = i;
int rt=0;
for(int j=1;j<=p;++j) {
if(!ch[rt][str[j] - ‘a‘])
ch[rt][str[j] - ‘a‘] = ++tot;
rt=ch[rt][str[j] - ‘a‘];
}
fin[i] = rt;
if(p < B) {
rt=0;
for(int j=1;j<=p;++j) {
if(!c2[rt][str[j] - ‘a‘]) {
c2[rt][str[j] - ‘a‘] = ++nod;
}
rt = c2[rt][str[j] - ‘a‘];
}
ind[rt].pb(i);
}
}
// 建立完 AC 自动机.
build(),calcf();
for(int i=1;i<=Q;++i) {
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
ll ans = 0ll;
if(id[k]) {
ans += (ll)(f[id[k]][r] - f[id[k]][l-1]);
}
if(ss[k].size() - 1 < B) {
for(int j=1;j<ss[k].size();++j) {
int rt=c2[0][ss[k][j]];
for(int h=j;h<ss[k].size();++h) {
if(!rt) {
break;
}
// 处理到 h=1;
if(ind[rt].size()) {
int L=lower_bound(ind[rt].begin(), ind[rt].end(), l)-ind[rt].begin();
int R=lower_bound(ind[rt].begin(), ind[rt].end(), r+1)-ind[rt].begin();
// [L, R)
if(R>L) {
ans += (ll)(R - L);
}
}
if(h == ss[k].size() - 1) break;
rt = c2[rt][ss[k][h + 1]];
}
}
}
printf("%lld\n", ans);
}
return 0;
}
原文：https://www.cnblogs.com/brady12/p/15313502.html