AC 自动机 60pts TLE 求调

#include<bits/stdc++.h>
using namespace std;
int n,q;
struct node{
    int son[27],fail,cnt,sum;
}tr[5000005];
int cnt;
vector<int> e[5000005],to;
string change(string a,string b){
    int l,r;
    string c;
    for(l=0;l<a.size()&&a[l]==b[l];l++);
    for(r=a.size()-1;r>=0&&a[r]==b[r];r--);
    for(int j=0;j<l;j++)c+=a[j];
    c+='z'+1;
    for(int j=l;j<=r;j++)c+=a[j];
    for(int j=l;j<=r;j++)c+=b[j];
    c+='z'+1;
    for(int j=r+1;j<a.size();j++)c+=a[j];
    return c;
}
void insert(string s){
    int p=0;
    for(auto i:s){if(!tr[p].son[i-'a'])tr[p].son[i-'a']=++cnt;p=tr[p].son[i-'a'];}
    tr[p].cnt++;
}
void build(){
    queue<int> q;
    for(int i=0;i<27;i++){if(tr[0].son[i])q.push(tr[0].son[i]);}
    while(!q.empty()){
        int p=q.front();
        for(int i=0;i<27;i++){if(tr[p].son[i])tr[tr[p].son[i]].fail=tr[tr[p].fail].son[i],q.push(tr[p].son[i]);else tr[p].son[i]=tr[tr[p].fail].son[i];}
        q.pop();
    }
}
void top(){
    queue<int> q;
    q.push(0);
    while(!q.empty()){int p=q.front();to.push_back(p);for(auto i:e[p])q.push(i);q.pop();}
}
int query(string x){
    for(int i=0;i<=cnt;i++)tr[i].sum=0;
    int p=0;
    for(auto i:x){p=tr[p].son[i-'a'];tr[p].sum++;}
    for(int i=to.size()-1;i>=0;i--){tr[tr[to[i]].fail].sum+=tr[to[i]].sum;}
    int res=0;
    for(int i=1;i<=cnt;i++)res+=tr[i].sum*tr[i].cnt;
    return res;
}
int main(){
    cin>>n>>q;
    for(int i=0;i<n;i++){
        string a,b,c;
        cin>>a>>b;
        if(a==b)continue;
        c=change(a,b);
        insert(c);
    }
    build();
    for(int i=1;i<=cnt;i++)e[tr[i].fail].push_back(i);
    top();
    for(int i=0;i<q;i++){
        string a,b,c;
        cin>>a>>b;
        if(a.size()!=b.size())cout<<"0\n";
        c=change(a,b);
        cout<<query(c)<<endl;
    }
    return 0;
}