rt,小样例过了，数据爆炸，求调或者给 HACK

思路见代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+114;
const int warma = 317;
const int maxsq = 400;
string s[maxn];
struct Query{
	Query(int L,int R,int ID){
		l=L,r=R,id=ID;
	}
	int l,r,id;
};
int n,q;
vector<Query> Q[maxn];
int answer[maxn];
int Hson[maxn*5],sz[maxn*5];
vector<int> type[maxn*5];
vector< pair<int,int> > w[maxn];
int L[maxn*5],R[maxn*5],Node[maxn*5];
int cnt[maxn];
class AC_automaton{
public:
    int son[maxn*5][26],fail[maxn*5],rt,tot,dfncnt;
    int sum[maxn*5];
    vector<int> edge[maxn*5];
    vector<int> fa[maxn];
    void init(){
    	memset(son,0,sizeof(son));
    	memset(fail,0,sizeof(fail));
    	memset(sum,0,sizeof(sum));
    	for(int i=0;i<maxn;i++) edge[i].clear();
		for(int i=1;i<=n;i++) fa[i].clear();
    	rt=tot=dfncnt=0;
	}
    void insert(string &s,int pos){
        int len=s.size(),now=rt;
        for(int i=0;i<len;i++){
            if(son[now][s[i]-'a']==0) son[now][s[i]-'a']=++tot;
            now=son[now][s[i]-'a'];
            fa[pos].push_back(now);
            sz[now]++;
            type[now].push_back(pos);
        }
    }
    void build(){
        queue<int> q;
        for(int i=0;i<26;i++) if(son[rt][i]) fail[son[rt][i]]=rt,q.push(son[rt][i]);
        while(q.size()>0){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(son[u][i]){
                    fail[son[u][i]]=son[fail[u]][i];
                    q.push(son[u][i]);
                }
                else son[u][i]=son[fail[u]][i];
            }
        }
        for(int i=1;i<=tot;i++){
        	edge[fail[i]].push_back(i);	
		}
    }
    void dfs(int u){
    	L[u]=R[u]=++dfncnt;
		Node[dfncnt]=u;
		for(int v:edge[u]){
			dfs(v);
			R[u]=max(R[v],R[u]);
			sum[u]+=sum[v];
			sz[u]+=sz[v];
			if(Hson[u]==-1||sz[v]>sz[Hson[u]]) Hson[u]=v;
		} 
	}
	void dsu(int u,bool keep){//dsu on tree
		for(int v:edge[u]){
			if(v!=Hson[u]) dsu(v,false);
		}
		if(Hson[u]!=-1) dsu(Hson[u],true);
		for(int v:edge[u]){
			if(v!=Hson[u]){
				for(int i=L[v];i<=R[v];i++){
					for(int x:type[Node[i]]) cnt[x]++;
				}
			}
		}
		for(int x:type[u]) cnt[x]++;
		for(int x:type[u]){
			w[x].push_back(make_pair(u,cnt[x]));
		}
		if(keep==false){
			for(int i=L[u];i<=R[u];i++){
				for(int x:type[Node[i]]) cnt[x]--;
			}
		}
	}
}AC;
class Block{
private:
	int tag[maxsq],a[maxn];
public:
	void cover(int l,int r,int v);
	int query(int x);
}chifan;
void Block::cover(int l,int r,int v){
	int bl=(l-1)/warma+1,br=(r-1)/warma+1;
	if(bl==br){
		for(int i=l;i<=r;i++) a[i]=max(a[i],v);
		return ;
	}
	for(int i=bl+1;i<br;i++) tag[i]=max(tag[i],v);
	for(int i=l;i<=bl*warma;i++) a[i]=max(a[i],v);
	for(int i=(br-1)*warma+1;i<=r;i++) a[i]=max(a[i],v);
}
int Block::query(int x){
	return max(a[x],tag[(x-1)/warma+1]);
}
struct ASK{
	int l,k,id;
	ASK(int L,int K,int ID){
		l=L,k=K,id=ID;
	}
}; 
int tr[maxn<<2];
void build(int cur,int lt,int rt){
	if(lt==rt){
		tr[cur]=AC.sum[AC.fa[lt].back()];
		return ;
	}
	int mid=(lt+rt)>>1;
	build(cur<<1,lt,mid);
	build(cur<<1|1,mid+1,rt);
	tr[cur]=max(tr[cur<<1],tr[cur<<1|1]);
}
int query_mx(int cur,int l,int r,int lt,int rt){
	if(l<=lt&&rt<=r) return tr[cur];
	if(r<lt||l>rt) return 0;
	int mid=(lt+rt)>>1;
	return max(query_mx(cur<<1,l,r,lt,mid),query_mx(cur<<1|1,l,r,mid+1,rt));
}
vector<ASK> ask[maxn];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(Hson,-1,sizeof(Hson));
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=q;i++){
		int l,r,k;
		cin>>l>>r>>k;
		if(s[k].size()<=warma){
			ask[r].push_back(ASK(l,k,i));
		}
		else{
			Q[k].push_back(Query(l,r,i));
		}
	}
	AC.init();
	for(int i=1;i<=n;i++) AC.insert(s[i],i);
	AC.build();
	AC.dfs(AC.rt);
	AC.dsu(AC.rt,true);
	for(int i=1;i<=n;i++){
		chifan.cover(L[AC.fa[i].back()],R[AC.fa[i].back()],i);
		for(ASK now:ask[i]){
			for(pair<int,int> u:w[now.k]){
				if(chifan.query(L[u.first])>=now.l) answer[now.id]=max(answer[now.id],u.second);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(Q[i].size()>0){
			AC.init();
			memset(tr,0,sizeof(tr));
			for(int i=1;i<=n;i++) AC.insert(s[i],i);
			AC.build();
			for(int u:AC.fa[i]){
				AC.sum[u]++;
			}
			AC.dfs(AC.rt);
			build(1,1,n);
			for(Query now:Q[i]){
				answer[now.id]=query_mx(1,now.l,now.r,1,n);
			}
		}
	}
	for(int i=1;i<=q;i++) cout<<answer[i]<<'\n';
	return 0;
}
/*
2 1
aa
a
1 2 1
*/