Codeforces

Luogu

分析

考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。

将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,M=500000+10;

int n,Q; char s[N];

int ch[N][26],fa[N],fail[N],pos[N],tot=0;
inline void insert(char* s,int id) {
    int l=strlen(s+1),now=0;
    for (re int i=1;i<=l;++i) {
        int w=s[i]-'a';
        if (!ch[now][w]) ch[now][w]=++tot,fa[tot]=now;
        now=ch[now][w];
    }
    pos[id]=now;
}
inline void getfail() { queue<int> Q;
    for (re int i=0;i<26;++i) if (ch[0][i]) Q.push(ch[0][i]);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re 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];
        }
    }
}

struct edge { int v,nxt; } e[N];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int L[N],R[N],tim=0;
inline void dfs(int u) {
    L[u]=++tim;
    for (re int i=head[u];i;i=e[i].nxt) dfs(e[i].v);
    R[u]=tim;
}

int c[N];
inline void add(int x,int y) { for (;x<=tot+1;x+=x&-x) c[x]+=y; }
inline int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

struct query { int u,w,id; };
vector<query> q[N];
int ans[M];

int main() {
    n=read(),Q=read();
    for (re int i=1;i<=n;++i) scanf("%s",s+1),insert(s,i);
    getfail();
    for (re int i=1;i<=tot;++i) addEdge(fail[i],i);
    dfs(0);
    for (re int i=1;i<=Q;++i) {
        int l=read(),r=read(),k=read();
        q[l-1].push_back((query){pos[k],-1,i});
        q[r].push_back((query){pos[k],1,i});
    }
    for (re int i=1;i<=n;++i) {
        for (re int j=pos[i];j;j=fa[j]) add(L[j],1);
        for (re auto j:q[i])
            ans[j.id]+=j.w*(sum(R[j.u])-sum(L[j.u]-1));
    }
    for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}