题目传送门
题意分析
将一个变换 \(S_1\to S_2\) 表示为 \(ABC\to ADC\)，其中 \(A,C\) 是最长公共前后缀，那么将其转换为 \(A?BD?C\)，其中 \(?\) 为特殊字符。\(T_1\to T_2\) 同理。直接跑多模匹配即可。用 AC 自动机解决，时间复杂度线性乘字符集大小。
AC 自动机
记 \((s_{i,1},s_{i,2})\) 转化为的字符串为 \(s_i\)，\((t_{i,1},t_{i,2})\) 转化为的字符串为 \(t_i\)。
考虑多模式串匹配多文本串如何做到正确的复杂度。
但文本串是简单的 AC 自动机，跑一遍之后按照 fail 指针倒序合并信息即可。
但是本题需要多文本串，对于 \(q\) 个文本串，如果每一次都全部清空，再 \(\mathcal O(L_1)\) 倒序合并，复杂度就是错的。
因此考虑优化一下 AC 自动机。容易发现仅仅需要统计能够与 \(t_i\) 匹配的 \(s_i\) 的数量。因此对于走到的点 \(p\)，记 \(p\) 的 fail 指针形成的到根节点的链上所有节点的 \(\textit{id}\) 之和为 \(x\)，那么 \(p\) 对于答案的贡献为 \(\textit{cnt}\cdot x\)。
其中，\(\textit{id}\) 表示一个节点被标记为 \(s_i\) 末尾节点的次数，\(\textit{cnt}\) 表示 \(p\) 被 \(t_i\) 走过的次数。
这样，每次也不需要清空所有节点，时间戳优化即可。
最终时间复杂度 \(\mathcal O((L_1+L_2)V)\)，\(V\) 表示字符集大小，有 \(V=27\)。
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e5,Q=2e5,V=27,L=5e6;
constexpr const char eps='?';
int n,q;
string calc(const string &a,const string &b){int l=0;while(l<a.size()&&a[l]==b[l]){l++;}string pre=a.substr(0,l);string suf;int r=a.size()-1;while(l<r&&a[r]==b[r]){r--;}return a.substr(0,l)+eps+a.substr(l,r-l+1)+b.substr(l,r-l+1)+eps+a.substr(r+1,a.size()-1-r);
}
struct AC{int size,Tag;struct node{int id,fail,cnt,tag,depth;int m[V+1];}t[L+1];int hash(char x){if('a'<=x&&x<='z'){return x-'a';}else{return 26;}}void insert(const string &s){int p=0;for(char i:s){if(!t[p].m[hash(i)]){t[p].m[hash(i)]=++size;}p=t[p].m[hash(i)];}t[p].id++;}int q[L+1],front,rear;void build(){for(int i=0;i<V;i++){if(t[0].m[i]){q[rear++]=t[0].m[i];}}while(front<rear){int x=q[front++];t[x].depth=t[t[x].fail].depth+t[x].id;for(int i=0;i<V;i++){if(t[x].m[i]){t[t[x].m[i]].fail=t[t[x].fail].m[i];q[rear++]=t[x].m[i];}else{t[x].m[i]=t[t[x].fail].m[i];}}}}int query(string s){int p=0,ans=0;Tag++;vector<int>path;for(char i:s){p=t[p].m[hash(i)];if(t[p].tag!=Tag){t[p].cnt=0;t[p].tag=Tag;}t[p].cnt++;path.push_back(p);}sort(path.begin(),path.end());path.resize(unique(path.begin(),path.end())-path.begin());for(int i:path){ans+=t[i].cnt*t[i].depth;}return ans;}
}AC;
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++){string a,b;cin>>a>>b;if(a==b){n--,i--;continue;}AC.insert(calc(a,b));}AC.build();for(int i=1;i<=q;i++){string a,b;cin>>a>>b;cout<<AC.query(calc(a,b))<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}