1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=6e5+10;
const double eps=1e-8;
const int mod=1e9+9;
#define ll long long
using namespace std;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
string str[MAXN];
int n,m;
int rt,cnt,cur;
int dis[MAXN],ch[MAXN][26],fa[MAXN],tag[MAXN];
void built(int x,int id){
int last=cur;cur=++cnt;dis[cur]=dis[last]+1;tag[cur]=id;int p=last;
for(;p&&!ch[p][x];p=fa[p])ch[p][x]=cur;
if(!p)fa[cur]=rt;
else{
int q=ch[p][x];
if(dis[q]==dis[p]+1)fa[cur]=q;
else{
int nt=++cnt;dis[nt]=dis[p]+1;
memcpy(ch[nt],ch[q],sizeof(ch[q]));
fa[nt]=fa[q];fa[q]=fa[cur]=nt;
for(;ch[p][x]==q;p=fa[p])ch[p][x]=nt;
}
}
}
int id[MAXN];
void solve(){
inc(i,1,n){
int len=str[i].size();int temp=rt;
for(int j=0;j<len;j++){
int t=str[i][j]-'a';
if(ch[temp][t])temp=ch[temp][t];
else{
int p=temp;
for(;p&&!ch[p][t];p=fa[p]);
if(!p)temp=rt;else temp=ch[p][t];
}
}
id[i]=temp;
}
}
int dfn[MAXN],tot,num[MAXN],fdfn[MAXN];
void dfs(int x){
dfn[x]=++tot;num[x]=1;fdfn[tot]=x;
link(x){
dfs(j->t);
num[x]+=num[j->t];
}
}
typedef struct node{
int l,r,sum;
}node;
node d[MAXN*21];int Rt[MAXN],tot1;
void update(int &x,int y,int l,int r,int t){
x=++tot1;d[x]=d[y];d[x].sum++;
if(l==r)return ;
int mid=(l+r)>>1;
if(t<=mid)update(d[x].l,d[y].l,l,mid,t);
else update(d[x].r,d[y].r,mid+1,r,t);
}
int ans;
void query(int x,int y,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){ans+=d[y].sum-d[x].sum;return ;}
int mid=(l+r)>>1;
if(ql<=mid)query(d[x].l,d[y].l,l,mid,ql,qr);
if(qr>mid)query(d[x].r,d[y].r,mid+1,r,ql,qr);
}
int main(){
ios::sync_with_stdio(false);
rt=cur=cnt=1;
cin>>n>>m;
inc(i,1,n)cin>>str[i];
inc(i,1,n){
int len=str[i].size();
cur=1;
for(int j=0;j<len;j++)built(str[i][j]-'a',i);
}
solve();
inc(i,1,cnt)add(fa[i],i);
dfs(rt);
inc(i,1,tot){
if(!tag[fdfn[i]])Rt[i]=Rt[i-1];
else update(Rt[i],Rt[i-1],1,n,tag[fdfn[i]]);
}
int l,r,x;
while(m--){
cin>>l>>r>>x;x=id[x];
ans=0;query(Rt[dfn[x]-1],Rt[dfn[x]+num[x]-1],1,n,l,r);
printf("%d\n",ans);
}
return 0;
}
|