题意分析
将一个变换 $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 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//#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;
}
