好牛的题，但是题解区怎么没我看得懂的题解啊/kk

我们发现，如果每次询问我们都能把这个区间拉出来跑 ACAM 那就赢了，这样做的复杂度高主要是因为每次询问的区间串长得非常不一样，信息没有很好的利用到！

我们考虑把某一部分的区间弄成一些长得比较相似的东西放在一起做，以降低复杂度。

于是人类智慧地，我们找到区间 $[l,r]$ 中最右的 $x$，满足存在 $y\in [1,l)$ 使得 $t[y\sim x]$ 是某个 $s_i$。

如果我们找到了这个东西，我们就赢了。因为我们注意到，$[l,y]$ 是 $s_i$ 的后缀！那么 $[l,y]$ 内部的贡献我们可以预处理出来。

也就是我们对每个 $s_i$ 都进行一个匹配，通过处理出 fail 树的深度等信息，可以快速知道某个串种出现了多少次模式串，但是这里是后缀，所以我们对其反转一下就可以了。这个均摊复杂度是对的，也就是上文中说的，我们找到了这些长得比较相似的串统一处理，使复杂度更优。

当我们找到这个 $i$ 的时候，我们就可以直接拿这个 $i$ 中已经预处理好的信息算答案了。

那么此时 $[l,y]$ 内部已经处理完了，而右端点在 $[y+1,r]$ 的贡献，只需要直接按照前缀匹配做就行，因为它们不存在左端点在 $l$ 左边的不合法匹配，所以直接做就是对的！

而找 $y,i$ 也是简单的，我们可以处理出 fail 树上最长的匹配和编号，那么我们就可以知道 $[1,i]$ 这个前缀最左边匹配的位置在哪里，查询只需要线段树二分即可。

那么时间复杂度就可以做到 $O(S+|t|+m\log |t|)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1000010;
vector<int>qwq[N];
struct ACAM{
	int tr[N][26],fail[N],vis[N];
	int in[N],dep[N],mx[N],id[N],sx[N];
	int tot,tp[N];
	void insert(string s,int awa){
		int p=0;
		int len=s.size();
		for(int i=0;i<len;i++){
			int ch=s[i]-'a';
			if(!tr[p][ch])tr[p][ch]=++tot;
			p=tr[p][ch];
		}
		vis[p]=len;sx[p]=awa;
	}
	void build(){
		queue<int>q;
		for(int i=0;i<26;i++)
			if(tr[0][i])
				q.push(tr[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<26;i++){
				if(tr[u][i]){
					fail[tr[u][i]]=tr[fail[u]][i];
					q.push(tr[u][i]);
				}else{
					tr[u][i]=tr[fail[u]][i];
				}
			}
		}
		for(int i=1;i<=tot;i++)
			in[fail[i]]++;
		for(int i=1;i<=tot;i++){
			if(!in[i]){
				q.push(i);
			}
		}
		int qwq=0;
		while(!q.empty()){
			int u=q.front();q.pop();
			tp[++qwq]=u;
			if(!(--in[fail[u]])){
				q.push(fail[u]);
			}
		}
		for(int i=qwq;i>=1;i--){
			dep[tp[i]]=dep[fail[tp[i]]]+(vis[tp[i]]!=0);
			if(vis[tp[i]]>mx[fail[tp[i]]])
				mx[tp[i]]=vis[tp[i]],id[tp[i]]=tp[i];
			else
				mx[tp[i]]=mx[fail[tp[i]]],id[tp[i]]=id[fail[tp[i]]];
		}		
	}
}T1,T2;

int pos[N*5];
struct Tree{
	int tr[N*20];
	void build(int l,int r,int p){
		if(l==r){
			tr[p]=pos[l];
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,p<<1);
		build(mid+1,r,p<<1|1);
		tr[p]=min(tr[p<<1],tr[p<<1|1]);
	}
	int find(int l,int r,int p,int x){
		if(tr[p]>=x)return -1;
		if(l==r)return l;
		int mid=(l+r)>>1;
		if(tr[p<<1|1]<x)return find(mid+1,r,p<<1|1,x);
		else return find(l,mid,p<<1,x);
	}
	int query(int l,int r,int p,int a,int b,int x){
		if(l>b||r<a)return -1;
		if(a<=l&&r<=b)return find(l,r,p,x);
		int mid=(l+r)>>1;
		int tmp=query(mid+1,r,p<<1|1,a,b,x);
		if(tmp!=-1)return tmp;
		return query(l,mid,p<<1,a,b,x);
	}
}T;
char t[N*5];
string s[N];
int pre[N*5],pwp[N*5];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	cin>>t+1;
	int len=strlen(t+1);
	for(int i=1;i<=n;i++){
		cin>>s[i];
		T1.insert(s[i],i);
		reverse(s[i].begin(),s[i].end());
		T2.insert(s[i],i);
	}
	T1.build();T2.build();
	int p=0;
	for(int i=1;i<=len;i++){
		p=T1.tr[p][t[i]-'a'];
		pre[i]=pre[i-1]+T1.dep[p];
		pos[i]=i-T1.mx[p]+1;
		pwp[i]=T1.sx[T1.id[p]];
	}
	T.build(1,len,1);
	for(int i=1;i<=n;i++){
		p=0;
		int w=s[i].size();
		qwq[i].resize(w+1);
		for(int j=0;j<w;j++){
			p=T2.tr[p][s[i][j]-'a'];
			qwq[i][j]=(j?qwq[i][j-1]:0)+T2.dep[p];
		}
	} 
	while(m--){
		int l,r;
		cin>>l>>r;
		int ps=T.query(1,len,1,l,r,l);
		if(ps==-1){
			cout<<pre[r]-pre[l-1]<<' ';
			continue;
		}
		int ans=pre[r]-pre[ps]+qwq[pwp[ps]][ps-l];
		cout<<ans<<' '; 
	}
	return 0;
}