疑问，空间是否影响效率

#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+5,MR=5e6+5;
const uint64_t P=257;
int n,q;
int ans[NR];
string s1[NR],s2[NR],t1[NR],t2[NR];
int ls[NR],rs[NR],lt[NR],rt[NR];

tuple<uint64_t,int,int> Hash(const string& s1,const string& s2){//将ABC，ADC中间的BD哈希值取出 
	int l=0,r=s1.size()-1;
	while(l<s1.size()&&s1[l]==s2[l]) l++;
	while(r>=0&&s1[r]==s2[r]) r--;
	if(r<l) return make_tuple(0,-1,-1);
	uint64_t ret=0;
	for(int i=l;i<=r;i++){
		ret=ret*P+s1[i];
	} 
	for(int i=l;i<=r;i++){
		ret=ret*P+s2[i];
	}
	return make_tuple(ret,l,r);
}
unordered_map<uint64_t,vector<int>> fs,ft;

struct Trie{
	int ch[MR][27],sz,root;
	int fa[MR];
	Trie(){
		sz=-1,root=0;
		memset(ch,0,sizeof(ch));
	}
	int insert(const string& s,int r){
		int cur=root;
		if(!ch[cur][26]) ch[cur][26]=++sz;
		cur=ch[cur][26];
		fa[cur]=root;
		for(int i=r+1;i<s.size();i++){
			if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a']=++sz;
			fa[ch[cur][s[i]-'a']]=cur;
			cur=ch[cur][s[i]-'a'];
		}
		return cur;
	}
	int insertr(const string& s,int l){
		int cur=root;
		if(!ch[cur][26]) ch[cur][26]=++sz;
		cur=ch[cur][26];
		fa[cur]=root;
		for(int i=l-1;i>=0;i--){
			if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a']=++sz;
			fa[ch[cur][s[i]-'a']]=cur;
			cur=ch[cur][s[i]-'a'];
		}
		return cur;
	}
}f1,f2;
vector<int> id[MR];//f1
vector<pair<int,int>> g[MR];//f1
int cnt[MR];//f2;
void dfs(int x){
	for(auto e:id[x]){
		cnt[e]++;
	}
	for(auto e:g[x]){
		int p=e.first;
		while(p!=f2.root){
			ans[e.second]+=cnt[p];
			p=f2.fa[p];
		}
	}
	for(int i=0;i<27;i++){
		if(!f1.ch[x][i]) continue;
		dfs(f1.ch[x][i]);
	}
	for(auto e:id[x]){
		cnt[e]--;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>s1[i]>>s2[i];
		uint64_t h;
		tie(h,ls[i],rs[i])=Hash(s1[i],s2[i]);
		if(h==0) continue;
		fs[h].push_back(i);
	}
	for(int i=1;i<=q;i++){
		cin>>t1[i]>>t2[i];
		if(t1[i].size()!=t2[i].size()){
			ans[i]=0;
			continue;
		}
		uint64_t h;
		tie(h,lt[i],rt[i])=Hash(t1[i],t2[i]);
		ft[h].push_back(i);
	}
	for(auto e:fs){
		uint64_t h=e.first;
		f1.root=++f1.sz;
		f2.root=++f2.sz;
		for(auto i:e.second){
			int p=f1.insertr(s1[i],ls[i]);
			int x=f2.insert(s1[i],rs[i]);
			id[p].push_back(x);
		}
		for(auto i:ft[h]){
			int p=f1.insertr(t1[i],lt[i]);
			int x=f2.insert(t1[i],rt[i]);
			g[p].push_back(make_pair(x,i));
		}
		dfs(f1.root);
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}