trie套trie求hack

#include<bits/stdc++.h>
using namespace std;
using H=unsigned long long;
const H B=29;
template<typename Value>
struct trie{
	struct node{
		Value v;
		node*ch[26];
		node(){v=Value();fill(ch,ch+26,nullptr);}
	}*rt;
	trie(){rt=0;}
	Value&insert(node*&u,const string&s,const int&i){
		if(!u)u=new node;
		if(s.size()==i)return u->v;
		return insert(u->ch[s[i]-'a'],s,i+1);
	}Value&insert(const string&s){return insert(rt,s,0);}
};
unordered_map<H,unordered_map<H,trie<trie<int>>>>tr;
int n,q;
string s,t;
int find1(const trie<int>&tr,const string&s){
	auto u=tr.rt;
	int ans=0;
	for(const char&c:s){
		if(!u)return ans;
		ans+=u->v;
		u=u->ch[c-'a'];
	}if(u)ans+=u->v;
	return ans;
}int find2(const trie<trie<int>>&tr,const string&s,const string&t){
	auto u=tr.rt;
	int ans=0;
	for(const char&c:s){
		if(!u)return ans;
		ans+=find1(u->v,t);
		u=u->ch[c-'a'];
	}if(u)ans+=find1(u->v,t);
	return ans;
}signed main(){
	cin>>n>>q;
	for(;n--;){
		cin>>s>>t,s=' '+s,t=' '+t;
		if(s==t)continue;
		int x=1,y=s.size()-1;
		string a,b;
		H c=0,d=0;
		for(;s[x]==t[x];++x)a+=s[x];
		for(;s[y]==t[y];--y)b+=s[y];
		for(int i=x;i<=y;++i)c=c*B+s[i]-'a'+1,d=d*B+t[i]-'a'+1;
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		++tr[c][d].insert(a).insert(b);
	}for(;q--;){
		cin>>s>>t,s=' '+s,t=' '+t;
		if(s.size()!=t.size()){cout<<"0\n";continue;}
		int x=1,y=s.size()-1;
		string a,b;
		H c=0,d=0;
		for(;s[x]==t[x];++x)a+=s[x];
		for(;s[y]==t[y];--y)b+=s[y];
		for(int i=x;i<=y;++i)c=c*B+s[i]-'a'+1,d=d*B+t[i]-'a'+1;
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		cout<<find2(tr[c][d],a,b)<<'\n';
	}
}