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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-22 19:52
 * update_at: 2026-10-15 11:26
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 枚举每条规则和每个起点，检查替换后是否等于目标串，只适合很小的数据。
//
// ==================== 教学导读 ====================
// 【题目在问什么】给定 n 条规则 (s1, s2)（等长），每次询问给两个不等的等长串
// t1、t2，问有多少种「方案」把 t1 变成 t2。一个方案 = (规则编号 id, 替换起点 start)，
// 即把 t1[start .. start+|s1|-1] 换成 s2。不同 id 或不同 start 都算不同方案。
//
// 【暴力思路】不放过任何可能性：双重循环枚举所有 (id, start) 对，对每一对
// 模拟这次替换，看结果是否恰好等于 t2。因为题目要求“恰好一次替换”，
// 所以 (id, start) 就是方案的完整描述，枚举它们就等于枚举了所有方案。
//
// 【为什么正确】can_replace_at 做了两件完整的事：
//   ① 确认 t1 的 [start, start+len) 真的等于规则左串（否则这次替换根本不合法）；
//   ② 把区间换成规则右串后，整个结果串逐位和 t2 比较。
// 只要有一对 (id, start) 通过检查，答案就 +1，不多不少。
//
// 【复杂度】O(q * n * m * len)，m 是询问串长。只够测试点 1、2 的小数据，
// 但它是最容易看懂的版本，也是后面所有优化的正确性参照（对拍用）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105; // 只服务测试点 1、2 的小数据

int n, q;
string left_part[MAXN];  // 规则 i 的替换前串 s1
string right_part[MAXN]; // 规则 i 的替换后串 s2

// 检查把 a 的 [start, start+len) 子串用规则 id 替换后是否恰好等于 b。
// 先验证被替换区间与规则左串逐位相同，再验证替换后的整串与 b 逐位相同。
// 返回 true 就代表 (id, start) 是一个合法方案。
bool can_replace_at(const string &a, const string &b, int id, int start) {
    int len = left_part[id].size();
    int alen = a.size();
    if (start + len > alen) {
        return false; // 替换区间越出串尾，不合法
    }

    // 被替换区间必须与规则的替换前串完全相同
    for (int i = 0; i < len; i++) {
        if (a[start + i] != left_part[id][i]) {
            return false;
        }
    }

    // 替换区间外保持原样，区间内换成替换后串，逐位和 b 比较
    for (int i = 0; i < alen; i++) {
        char after_char = a[i];
        if (start <= i && i < start + len) {
            after_char = right_part[id][i - start];
        }
        if (after_char != b[i]) {
            return false;
        }
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    // 规则编号从 1 开始，和题面一致
    for (int i = 1; i <= n; i++) {
        cin >> left_part[i] >> right_part[i];
    }

    // 每个询问独立枚举「规则编号 + 替换起点」这一对，复杂度 O(q * n * len^2)。
    // 这一层枚举规则，里层枚举起点：两层合起来就是枚举所有可能的方案。
    while (q--) {
        string a, b;
        cin >> a >> b;

        ll ans = 0;
        // 替换不改变长度，长度不同必然无解
        if (a.size() == b.size()) {
            int alen = a.size();
            for (int id = 1; id <= n; id++) {
                int plen = left_part[id].size();
                for (int start = 0; start + plen <= alen; start++) {
                    if (can_replace_at(a, b, id, start)) {
                        ans++;
                    }
                }
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-14 23:06
 * update_at: 2026-10-15 11:26
 */
// anchor.cpp：首个差异对齐，每条规则只检查一个起点。
// 适用于中等数据及所有 q=1 的数据，一般数据下仍需逐询问扫描所有规则。
//
// ==================== 教学导读 ====================
// 【题目在问什么】给定 n 条规则 (s1, s2)（等长），每次询问给两个不等的等长串
// t1、t2，问有多少种「方案」把 t1 变成 t2。一个方案 = (规则编号 i, 替换起点 p)，
// 即把 t1[p..p+|s1|-1] 这个子串换成 s2。不同规则或不同起点都算不同方案。
//
// 【关键观察：首差对齐】t1 和 t2 只有在替换区间内才会不同，所以区间必须覆盖
// 所有不同位置。设规则左右串第一个不同位置是 d（0-based），询问两串第一个不同
// 位置是 L。替换起点是 p 时，规则的第 d 个字符恰好落在 t1 的 L 位置上，即
//         p + d = L   =>   p = L - d      （起点被唯一确定！）
// 于是每条规则最多只需要检查一个起点，不必枚举所有起点。
//
// 【怎么检查】起点 p 确定后要求：
//   ① 区间 [p, p+len-1] 不越界，且覆盖最后一个不同位置 R；
//   ② 区间内 t1 逐位等于规则左串、t2 逐位等于规则右串（区间外自动相同）。
// 两条都满足，这条规则就贡献一个方案。
//
// 【复杂度】预处理 O(L1)；每个询问 O(m + n * len)，总计 O(L1 + L2 + q * L1)。
// q = 1 时是线性的，但一般数据下 q 很大，需要后面的 Trie 分组做法。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Rule {
    string a, b;   // 规则的替换前串、替换后串
    ll first_diff; // 规则左右串第一个不同位置，0-based；-1 表示不改变字符
};

ll n, q;
vector<Rule> rules; // 所有规则，编号从 0 开始

// 判断规则 rule 能否在 t1=a 中恰好替换一次得到 t2=b。
// [L, R] 是 a、b 的首尾不同位置；规则若生效，替换起点只能由 L - first_diff 唯一确定。
// 随后要求整个替换区间落在串内、覆盖 R，并且区间内 a 匹配左串、b 匹配右串。
bool check_rule(const Rule &rule, const string &a, const string &b, ll L, ll R) {
    if (rule.first_diff == -1) return false;

    ll len = rule.a.size();
    ll m = a.size();
    ll start = L - rule.first_diff;
    // 起点唯一，且替换区间必须在串内并覆盖最后一个不同位置。
    if (start < 0 || start + len > m || start + len - 1 < R) return false;

    for (ll i = 0; i < len; i++) {
        if (a[start + i] != rule.a[i] || b[start + i] != rule.b[i]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    rules.resize(n);
    // 预处理每条规则的第一个差异位置，供 check_rule 反推唯一替换起点
    for (ll i = 0; i < n; i++) {
        cin >> rules[i].a >> rules[i].b;
        rules[i].first_diff = -1;
        ll len = rules[i].a.size();
        for (ll j = 0; j < len; j++) {
            if (rules[i].a[j] != rules[i].b[j]) {
                rules[i].first_diff = j;
                break;
            }
        }
    }

    while (q--) {
        string a, b;
        cin >> a >> b;
        // 替换不改变长度
        if (a.size() != b.size()) {
            cout << 0 << '\n';
            continue;
        }
        // 先求出询问两串的首尾不同位置 [L, R]：
        // 替换区间必须覆盖 [L, R]，否则区间外的差异改不掉。
        ll L = -1, R = -1;
        ll m = a.size();
        for (ll i = 0; i < m; i++) {
            if (a[i] != b[i]) {
                if (L == -1) L = i;
                R = i;
            }
        }
        ll answer = 0;
        // L = -1 表示两串完全相同，而题目保证 t1 != t2，答案必为 0。
        // 否则逐条规则检查那个「唯一可能的起点」，每条规则对答案至多贡献 1。
        if (L != -1) {
            for (ll i = 0; i < n; i++) {
                if (check_rule(rules[i], a, b, L, R)) answer++;
            }
        }
        cout << answer << '\n';
    }
    return 0;
}

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-14 23:06
 * update_at: 2026-10-15 11:26
 */
// special_b.cpp：仅适用于特殊性质 B：每个字符串恰好有一个 b，其余全为 a。
// 按 b 的位移分组，二维偏序用排序扫描和树状数组计数。
//
// ==================== 教学导读 ====================
// 【性质 B 的字符串长什么样】形如 aaabaaaa：只有一个 'b'，其余全是 'a'。
// 一条规则 (s1, s2) 能用，当且仅当把 s1 里的 b 挪到新位置（其余字符不变）
// 恰好得到 s2。所以规则可以压缩成三个数：
//   delta = b 的位移（目标位置 - 原位置）、left = b 左边的 a 个数、right = 右边的 a 个数。
//
// 【规则何时能回答一个询问】设询问里 b 从位置 p 挪到 r（同样记 delta、left、right）：
//   ① delta 必须相同：整串的 b 要挪同样的距离才能对上；
//   ② 规则的 left <= 询问的 left：替换区间左边不能越过 t1 的开头（P 是 X 的后缀）；
//   ③ 规则的 right <= 询问的 right：替换区间右边不能越过 t1 的结尾（S 是 Y 的前缀）。
// 三个条件合起来：同 delta 组内是一个二维偏序计数（left、right 都要 <=）。
//
// 【怎么数】把所有规则和询问都变成事件，按 delta 分组；组内按 left 升序扫描，
// 扫到规则就把它的 right 加进树状数组，扫到询问就查 right <= 询问 right 的规则数。
// left 相等时规则排在询问前面，保证统计的是 "<=" 而不是 "<"。
//
// 【复杂度】O(L1 + L2 + (n+q) log(n+q))，只在性质 B 的数据上使用。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Event {
    ll delta; // b 的位移：目标位置 - 原位置（规则和询问必须相同才能互相匹配）
    ll left;  // 规则中 b 左侧的 a 数，或询问允许的上界（规则 left <= 询问 left）
    ll right; // 规则中 b 右侧的 a 数，或询问允许的上界（规则 right <= 询问 right）
    ll id;    // 0 表示规则，正数表示询问编号
};

ll n, q;
vector<Event> events;    // 规则事件 + 询问事件，按 delta 分组扫描
vector<ll> coordinates;  // 所有规则的 right，用于离散化
vector<ll> bit, answer;  // bit 是树状数组；answer[id] 是第 id 个询问的答案

// 事件排序：先按 delta 分组，组内按 left 升序，left 相同时规则排在询问前面，
// 从而保证统计的是 left_rule <= left_query。
bool cmp_event(const Event &a, const Event &b) {
    if (a.delta != b.delta) return a.delta < b.delta;
    if (a.left != b.left) return a.left < b.left;
    return a.id < b.id; // left 相等时先加入规则，保证统计的是 <=
}

// 性质 B 保证每个串恰好有一个 'b'，返回它的下标；找不到返回 -1
ll find_b(const string &s) {
    ll len = s.size();
    for (ll i = 0; i < len; i++) {
        if (s[i] == 'b') return i;
    }
    return -1;
}

// 树状数组：按离散化后的 right 值单点加、前缀查
void bit_add(ll pos, ll value) {
    ll size = coordinates.size();
    for (; pos <= size; pos += pos & -pos) bit[pos] += value;
}

ll bit_query(ll pos) {
    ll result = 0;
    for (; pos > 0; pos -= pos & -pos) result += bit[pos];
    return result;
}

// 把规则事件的 right 离散化后计入树状数组；value=1 加入，value=-1 撤销
void add_rule(const Event &event, ll value) {
    ll pos = lower_bound(coordinates.begin(), coordinates.end(), event.right)
             - coordinates.begin() + 1;
    bit_add(pos, value);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    // 规则：记录 b 的位移 delta、左侧 a 数 left、右侧 a 数 right。
    // x == y 说明规则不改变字符串，不可能把 t1 变成不同的 t2，直接丢掉。
    for (ll i = 1; i <= n; i++) {
        string a, b;
        cin >> a >> b;
        ll x = find_b(a), y = find_b(b);
        if (x == y) continue; // 不改变字符串的规则不能回答 t1 != t2
        ll len = a.size();
        Event event;
        event.delta = y - x;
        event.left = x;
        event.right = len - 1 - x;
        event.id = 0;
        events.push_back(event);
        coordinates.push_back(event.right);
    }

    answer.assign(q + 1, 0);
    // 询问：把询问也转成同构事件，左、右均以 t1 中 b 的位置为准。
    // 同样丢掉 delta = 0（两串相同）或长度不同的询问，答案都是 0。
    for (ll i = 1; i <= q; i++) {
        string a, b;
        cin >> a >> b;
        if (a.size() != b.size()) continue;
        ll p = find_b(a), r = find_b(b);
        if (p == r) continue;
        ll len = a.size();
        Event event;
        event.delta = r - p;
        event.left = p;
        event.right = len - 1 - p;
        event.id = i;
        events.push_back(event);
    }

    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()), coordinates.end());
    bit.assign(coordinates.size() + 1, 0);
    sort(events.begin(), events.end(), cmp_event);

    // 按 delta 分组处理：组内二维偏序，处理完一组就撤销，避免不同 delta 互相干扰。
    // 扫描顺序保证：同 delta 里 left 小的规则先入树状数组，能回答 left 更大的询问。
    ll size = events.size();
    for (ll begin = 0; begin < size; ) {
        ll end = begin;
        while (end < size && events[end].delta == events[begin].delta) end++;

        for (ll i = begin; i < end; i++) {
            if (events[i].id == 0) {
                add_rule(events[i], 1);
            } else {
                // 查询统计 right_rule <= right_query 的规则数
                ll pos = upper_bound(coordinates.begin(), coordinates.end(), events[i].right)
                         - coordinates.begin();
                answer[events[i].id] = bit_query(pos);
            }
        }
        // 撤销本组规则，避免不同 delta 之间相互贡献。
        for (ll i = begin; i < end; i++) {
            if (events[i].id == 0) add_rule(events[i], -1);
        }
        begin = end;
    }

    for (ll i = 1; i <= q; i++) cout << answer[i] << '\n';
    return 0;
}

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-15 09:53
 * update_at: 2026-10-15 21:26
 */
// main.cpp：map 精确分组差异核心，每组普通插入左右 Trie。
// 左 Trie DFS 激活规则，在右 Trie 沿父指针直接求和。
//
// ==================== 教学导读（主解思路） ====================
// 【前后缀分解】把一条非恒等规则写成 s1 = P + A + S，s2 = P + B + S：
//   (A, B) 是首尾差异之间的双串内容，叫「差异核心」；P 是不变前缀，S 是不变后缀。
// 把等长询问同样拆成 t1 = X + C + Y，t2 = X + D + Y（(C, D) 是它的差异核心）。
//
// 【关键观察】首尾差异都要对齐：替换起点 p 必须满足 p + l = L 且 p + r = R
// （l、r 是规则差异位置，L、R 是询问差异位置）。所以规则可用的充要条件是：
//   ① 差异核心相同：(A, B) == (C, D)；
//   ② P 是 X 的后缀（不变前缀紧贴核心向左匹配，且不越出串首）；
//   ③ S 是 Y 的前缀（不变后缀紧贴核心向右匹配，且不越出串尾）。
// 满足三条时替换起点唯一，答案贡献 1。
//
// 【怎么数】按差异核心分组，每组把规则和询问的两侧插入两棵普通 Trie：
//   左 Trie 插入反转后的不变前缀；右 Trie 插入正向不变后缀。
//   规则左终点是询问左终点的祖先，且规则右终点是询问右终点的祖先，才合法。
// DFS 左 Trie：进入节点时激活恰好挂在这里的规则，离开时撤销。
// 回答询问时，激活集合恰好是当前节点到根路径上全部规则；
// 再沿询问右终点到根求 weight 之和，筛出右侧同样匹配的规则。
//
// 【复杂度】设 T=L1+L2，分组 O(T log(n+1))，建树和左 DFS 为 O(26T)，
// 右侧查询总长度受 L2 限制。固定字母表下总时间 O(T log(n+1))，空间 O(T)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXGROUP = 200000 + 10; // 差异核心组数不超过规则数 n
const int MAXNODE = 5000000 + 10; // 规则与询问单侧总长度至多 5000000，另有两个根

// 普通 Trie：ch[c] 存字符 c 对应的孩子编号，0 表示没有。
// 节点编号至多 5000002，权重不超过 n，因此用 int。
struct Node {
    int ch[26]; // 'a' 到 'z' 的孩子
    int parent; // 父节点，右树求祖先链之和时使用
    int weight; // 右树：在这里结束的已激活规则数
};

struct Record {
    string a;      // 两侧内容均不改变，只需保存原串（a 是 t1 / s1，b 只用来找差异）
    int l, r;      // 首尾差异位置，0-based；[l, r] 外的字符替换前后不变
    int right;     // 右 Trie 的终点（右端匹配到的最深节点）
    int query_id; // 规则为 0，询问为原始询问编号
};

Node node[MAXNODE];
vector<int> record_ids[MAXNODE]; // 节点桶：左终点为 u 的记录编号，放在 record_ids[u]
vector<int> group_records[MAXGROUP]; // 核心组桶：属于第 g 组的记录编号
bool has_query[MAXGROUP]; // 询问桶：第 g 组是否包含询问
int node_cnt, group_cnt;
ll n, q;
map<pair<string, string>, int> core_id;
vector<Record> records(1); // 完整记录从编号 1 开始保存
vector<ll> answer;

int new_node(int parent) {
    node_cnt++;
    // 组间复用节点池，重新使用的节点必须清空全部孩子。
    for (int c = 0; c < 26; c++) node[node_cnt].ch[c] = 0;
    node[node_cnt].parent = parent;
    record_ids[node_cnt].clear(); // 节点编号复用时，挂载的记录也必须清空
    node[node_cnt].weight = 0;
    return node_cnt;
}

// 字符 ch 对应的孩子不存在时新建，否则直接走过去。
int get_child(int u, int ch) {
    if (node[u].ch[ch] == 0) node[u].ch[ch] = new_node(u);
    return node[u].ch[ch];
}

void read_record(int query_id) {
    string a, b;
    cin >> a >> b;
    if (a.size() != b.size()) return; // 替换不改变长度，不等长直接丢掉（答案为 0）
    // 求差异区间 [l, r]，它就是「差异核心」在原串中的位置
    int l = -1, r = -1;
    ll len = a.size();
    for (ll i = 0; i < len; i++) {
        if (a[i] != b[i]) {
            if (l == -1) l = i;
            r = i;
        }
    }
    if (l == -1) return; // 恒等规则不能得到不同的目标串

    // 用差异核心 (A, B) 作为分组键：只有核心相同的规则和询问才可能互相匹配
    pair<string, string> key(a.substr(l, r - l + 1), b.substr(l, r - l + 1));
    auto it = core_id.find(key);
    int g;
    if (it == core_id.end()) {
        if (query_id != 0) return; // 没有这个核心的规则，询问答案为 0
        g = ++group_cnt;
        core_id[key] = g;
    } else {
        g = it->second;
    }
    if (query_id != 0) has_query[g] = true; // 标记本组需要建 Trie 统计

    Record current;
    current.a = move(a);
    current.l = l;
    current.r = r;
    current.right = 0;
    current.query_id = query_id;
    records.push_back(move(current));
    int record_id = records.size() - 1;
    group_records[g].push_back(record_id);
}

// 规则和询问一起插入：左侧反转，右侧正向，空侧边对应根。
// 左 Trie 存「核心左边那段的反转」：P 是 X 的后缀 ⟺ rev(P) 是 rev(X) 的前缀，
// 规则左终点在询问左终点的祖先链上，就满足左侧条件。
// 右 Trie 存「核心右边那段」，同理用前缀关系表达「S 是 Y 的前缀」。
void build_group(int g, int left_root, int right_root) {
    // 建树阶段：依次插入本组记录，挂到左终点，并记住右终点。
    for (auto record_id : group_records[g]) {
        int u = left_root;
        for (ll i = records[record_id].l - 1; i >= 0; i--) {
            u = get_child(u, records[record_id].a[i] - 'a');
        }
        record_ids[u].push_back(record_id); // 把这条记录挂在左终点上

        u = right_root;
        ll len = records[record_id].a.size();
        for (ll i = records[record_id].r + 1; i < len; i++) {
            u = get_child(u, records[record_id].a[i] - 'a');
        }
        records[record_id].right = u;
    }
}

// 计数阶段：左侧的匹配由 DFS 路径保证，右侧沿祖先链求和。
void enter_node(int u) {
    // 同节点上的规则必须全部激活后，再回答这里的询问（规则之间不区分先后）。
    // 「激活」= 在右 Trie 的规则终点上 weight +1，表示这条规则当前可用。
    for (auto record_id : record_ids[u]) {
        if (records[record_id].query_id == 0) node[records[record_id].right].weight++;
    }
    for (auto record_id : record_ids[u]) {
        if (records[record_id].query_id != 0) {
            // 询问：沿右 Trie 父指针把 weight 加起来。
            // 只要规则的右端节点是 v 的祖先（含 v 本身），就满足「S 是 Y 的前缀」，
            // 左端条件已由当前激活集合保证，因此这个和就是答案。
            ll result = 0;
            for (int v = records[record_id].right; v != 0; v = node[v].parent) {
                result += node[v].weight;
            }
            answer[records[record_id].query_id] = result;
        }
    }
}

void leave_node(int u) {
    for (auto record_id : record_ids[u]) {
        if (records[record_id].query_id == 0) node[records[record_id].right].weight--;
    }
}

// 左 Trie 的递归 DFS：进入时激活规则并回答询问，访问完孩子后撤销。
// 激活集合恰好是当前节点到根路径上的全部规则。
void dfs_left(int u) {
    enter_node(u);
    for (int c = 0; c < 26; c++) {
        int v = node[u].ch[c];
        if (v != 0) dfs_left(v);
    }
    leave_node(u);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    records.reserve(n + q + 1);
    answer.assign(q + 1, 0);
    for (ll i = 1; i <= n; i++) read_record(0);
    for (ll i = 1; i <= q; i++) read_record(i);
    core_id.clear(); // 分组完成，释放核心字典，再处理各组的 Trie

    for (int g = 1; g <= group_cnt; g++) {
        if (!has_query[g]) continue;
        node_cnt = 0; // 组间复用节点池，只初始化实际用到的节点
        int left_root = new_node(0);
        int right_root = new_node(0);
        build_group(g, left_root, right_root);
        dfs_left(left_root);
    }
    for (ll i = 1; i <= q; i++) cout << answer[i] << '\n';
    return 0;
}

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-22 19:52
 * update_at: 2026-10-15 13:37
 */
// main2.cpp：把规则和询问都转成字符对串，用 AC 自动机匹配，
// 再在 fail 树上按长度阈值离线计数。
//
// ==================== 教学导读 ====================
// 【核心思想：一次扫描同时匹配所有规则】逐询问逐规则检查太慢，
// 换个看法：一条规则在起点 p 可用 ⟺ 对每个 k，t1[p+k] = s1[k] 且 t2[p+k] = s2[k]。
// 把 t1、t2 逐位合成「字符对串」T：T[i] = (a[i], b[i])（编码 0..675），
// 规则也合成字符对串 R：R[k] = (s1[k], s2[k])。那么规则在 p 可用
// ⟺ R 恰好是 T[p .. p+|R|-1] 这段子串 —— 就是普通的模式串匹配！
//
// 【还要覆盖差异区间 [L, R]】规则长度为 k、起点为 p 时，要求 [p, p+k-1] ⊇ [L, R]。
// 固定结束位置 i = p+k-1（i >= R），则 p = i-k+1 >= L，即 k >= i-L+1。
// 于是：以 i 结尾、长度 >= i-L+1 的规则，都恰好贡献一个方案。
//
// 【AC 自动机 + fail 树怎么数】所有规则插入 Trie 建 AC 自动机，扫描 T 时每个位置 i
// 得到一个状态 state(i)。state(i) 的 fail 祖先（含自身）恰好是「所有以 i 结尾的
// 匹配规则」。把 fail 反过来建树，规则终点就是一些节点，问题变成：
//   对每个 (state, 阈值 k0)：state 的 fail 祖先里，深度 >= k0 的终止节点有多少个？
// 对每个 i >= R 拆一个这样的子问题（阈值 k0 = i-L+1）。
//
// 【离线回答】把终止节点按深度降序、子问题按阈值降序排序，双指针推进：
// 深度足够的终止节点就把它的 fail 子树整体 +weight（用 DFS 序区间加），
// 查询 state 的 tin 位置单点值。这就是树状数组上的经典离线套路。
//
// 【图怎么存】Trie 和 fail 树都用「vector<int> g[maxn] 邻接表」存孩子：
//   trie_g[u] 是 u 的 Trie 孩子，边字符挂在孩子上（node[v].ch = 到 v 的边字符）；
//   fail_g[u] 是 u 在 fail 树上的孩子。
// 建完 Trie 后给每个节点的孩子按字符排序，find_child 用 lower_bound 二分查找，转移 O(log 676)。
// AC 自动机用 std::queue 做 BFS 建 fail 指针；fail 树分两步：先建树（build_fail_tree
// 只加边），再用递归 DFS 求 DFS 序（dfs_fail_tree），每一步都一眼能看懂。
// 注意：fail 树可能深达百万级（一条超长规则就是一条长链），递归需要大栈，
// 所以 main 开头用 raise_stack_limit() 把系统栈上限调到 256MB，防止爆栈。
//
// 【复杂度】O((L1+L2) log(L1+L2))，适用于全部数据。
#include <bits/stdc++.h>
#include <sys/resource.h> // 调大系统栈上限用（Linux 评测环境）
using namespace std;

typedef long long ll;

// Trie 只由规则建成：L1 = 规则左右串总长度 <= 5e6，单侧 <= 2.5e6，
// 所以节点数不超过 2500001。两个 vector<int> 邻接表各占 24 字节/节点。
const int MAXNODE = 2500000 + 10;

// 一个 Trie 节点。深度 = 到根路径上的字符数，即该节点对应字符对串的长度。
struct Node {
    int ch;     // 入边上的字符对编码 0..675；根没有入边，记 -1
    int depth;  // 深度 = 该节点对应字符对串的长度（就是规则长度）
    int fail;   // fail 指针
    int weight; // 终止权重：以该节点结尾的规则条数（相同规则不去重）
    int tin;    // fail 树 DFS 序：进入时间戳
    int tout;   // fail 树 DFS 序：离开时间戳，子树是区间 [tin, tout]
};

// Ask：一个离线子问题
// need：规则长度阈值（只统计深度 >= need 的终止节点）；
// state：询问扫描到的 AC 状态（所有以当前位置结尾的匹配规则都在它的 fail 祖先上）；
// id：原始询问编号（一个询问会拆出多个子问题，答案累加）
struct Ask {
    int need;
    int state;
    int id;
};

int n, q;

Node node[MAXNODE];         // 节点池，编号 0..node_cnt-1，0 是根
vector<int> trie_g[MAXNODE]; // trie_g[u]：u 的 Trie 孩子（vector<int> g[maxn] 存图）
vector<int> fail_g[MAXNODE]; // fail_g[u]：u 在 fail 树上的孩子（同一套存图方式）
int node_cnt;                // 已创建的节点数，新建节点的编号就是 node_cnt

int dfs_timer; // fail 树 DFS 序的时间戳

vector<int> terminal_nodes; // 所有终止节点
vector<Ask> asks;           // 所有离线子问题
vector<ll> answer;          // 每个询问的答案
vector<ll> bit;             // 树状数组（差分 + 单点查前缀）

// 一对字符 (a, b) 编码成 0..675 的新字符：
// 把「双串逐位相等」变成「单串子串匹配」，是本解法最关键的一步。
int code_pair(char a, char b) {
    return (a - 'a') * 26 + (b - 'a');
}

// 新建一个节点，入边字符为 ch，返回编号
int new_node(int ch) {
    int id = node_cnt;
    node_cnt++;
    node[id].ch = ch;
    node[id].depth = 0;
    node[id].fail = 0;
    node[id].weight = 0;
    node[id].tin = 0;
    node[id].tout = 0;
    return id;
}

// 建树时取 u 的 ch 孩子，不存在就新建。
// 此时孩子还没排序，线性扫一遍；建完 Trie 统一排序后才用 find_child 二分。
int get_or_add_child(int u, int ch) {
    for (size_t i = 0; i < trie_g[u].size(); i++) {
        int v = trie_g[u][i];
        if (node[v].ch == ch) {
            return v;
        }
    }
    int v = new_node(ch);
    node[v].depth = node[u].depth + 1;
    trie_g[u].push_back(v);
    return v;
}

// lower_bound 用的比较函数：元素是节点 id，查找值是字符，
// 比较时把节点 id 映射成它的入边字符再和 ch 比。
bool cmp_node_char(int v, int ch) {
    return node[v].ch < ch;
}

// 在 u 的孩子里二分查找字符 ch 对应的孩子，找不到返回 -1。
// 前提：trie_g[u] 已按 node[v].ch 升序排好（sort_children 做的）。
// lower_bound 返回第一个「入边字符 >= ch」的孩子，再确认它真的等于 ch。
int find_child(int u, int ch) {
    vector<int>::iterator it = lower_bound(trie_g[u].begin(), trie_g[u].end(), ch, cmp_node_char);
    if (it == trie_g[u].end() || node[*it].ch != ch) {
        return -1;
    }
    return *it;
}

// 把规则 (a, b) 的字符对串插入 Trie，终止节点权值 +1
void insert_pair_string(const string &a, const string &b) {
    int u = 0;
    int len = a.size();
    for (int i = 0; i < len; i++) {
        int ch = code_pair(a[i], b[i]);
        u = get_or_add_child(u, ch);
    }
    node[u].weight++;
}

// Trie 孩子按入边字符升序排序（比较函数不用 lambda）
bool cmp_child(int a, int b) {
    return node[a].ch < node[b].ch;
}

// 给每个节点的孩子排序，之后 find_child 可以二分查找
void sort_children() {
    for (int u = 0; u < node_cnt; u++) {
        if (trie_g[u].size() > 1) {
            sort(trie_g[u].begin(), trie_g[u].end(), cmp_child);
        }
    }
}

// 沿 fail 链走一步转移，返回下一个 AC 状态
int move_state(int u, int ch) {
    while (u != 0 && find_child(u, ch) == -1) {
        u = node[u].fail;
    }
    int v = find_child(u, ch);
    if (v == -1) {
        return 0;
    }
    return v;
}

// BFS 建 AC 自动机的 fail 指针，用 std::queue 逐层扩展
void build_ac_automaton() {
    queue<int> que;

    // 根的孩子 fail 指向根
    for (size_t i = 0; i < trie_g[0].size(); i++) {
        int v = trie_g[0][i];
        node[v].fail = 0;
        que.push(v);
    }

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (size_t i = 0; i < trie_g[u].size(); i++) {
            int v = trie_g[u][i];
            int ch = node[v].ch;

            // 求 fail[v]：从 fail[u] 出发沿 fail 链找能走字符 ch 的节点，
            // 找不到就落到根。这个节点就是 v 对应串的最长真后缀所在位置。
            int f = node[u].fail;
            while (f != 0 && find_child(f, ch) == -1) {
                f = node[f].fail;
            }
            int go = find_child(f, ch);
            if (go == -1) {
                node[v].fail = 0;
            } else {
                node[v].fail = go;
            }
            que.push(v);
        }
    }
}

// 建 fail 树：把每个非根节点挂到 fail 指针指向的节点下面，只加边，不遍历。
// fail 指针反向后恰好是一棵树（根是 0）：u 的 fail 祖先就是 u 到根的路径。
void build_fail_tree() {
    for (int i = 1; i < node_cnt; i++) {
        fail_g[node[i].fail].push_back(i);
    }
}

// 在 fail 树上递归求 DFS 序：u 的子树对应连续区间 [tin[u], tout[u]]。
// 直接写递归 DFS 最好懂；代价是递归深度 = fail 树深度，最坏可达百万级，
// 所以 main 一开始调用 raise_stack_limit() 把系统栈上限调大，防止爆栈。
void dfs_fail_tree(int u) {
    node[u].tin = ++dfs_timer;
    for (size_t i = 0; i < fail_g[u].size(); i++) {
        int v = fail_g[u][i];
        dfs_fail_tree(v);
    }
    node[u].tout = dfs_timer;
}

// 递归 DFS 的深度最坏可达百万级（fail 树可能是一条长链），默认 8MB 系统栈不够。
// 把栈的软上限提高到 256MB（Linux 评测环境有效，普通进程即可调软上限）。
// 硬上限不足 256MB 时只能调到硬上限；若评测环境完全不许调整，需换回显式栈。
void raise_stack_limit() {
    struct rlimit rl;
    getrlimit(RLIMIT_STACK, &rl);
    if (rl.rlim_max == RLIM_INFINITY || rl.rlim_max > 256 * 1024 * 1024) {
        rl.rlim_cur = 256 * 1024 * 1024;
    } else {
        rl.rlim_cur = rl.rlim_max;
    }
    setrlimit(RLIMIT_STACK, &rl);
}

// ---- 树状数组：区间加、单点查（差分实现）----

void bit_add(int pos, ll val) {
    int nbit = bit.size() - 1;
    while (pos <= nbit) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}

void bit_range_add(int l, int r, ll val) {
    bit_add(l, val);
    bit_add(r + 1, -val);
}

ll bit_query(int pos) {
    ll res = 0;
    while (pos > 0) {
        res += bit[pos];
        pos -= pos & -pos;
    }
    return res;
}

// 终止节点按深度从大到小排序
bool cmp_terminal_depth(int a, int b) {
    return node[a].depth > node[b].depth;
}

// 离线子问题按长度阈值从大到小排序
bool cmp_ask_need(const Ask &a, const Ask &b) {
    return a.need > b.need;
}

// 离线回答所有子问题：
// 深度不小于阈值的终止节点，其 fail 子树整体加权后，查状态的 DFS 序位置。
// 为什么查 tin[state] 就够：终止节点 u 加在 [tin[u], tout[u]] 上，
// u 是 state 的 fail 祖先 ⟺ state 在 u 的子树里 ⟺ tin[state] ∈ [tin[u], tout[u]]。
void answer_offline_asks() {
    bit.assign(node_cnt + 2, 0);

    sort(terminal_nodes.begin(), terminal_nodes.end(), cmp_terminal_depth);
    sort(asks.begin(), asks.end(), cmp_ask_need);

    int ptr = 0;
    int term_cnt = terminal_nodes.size();
    int ask_cnt = asks.size();
    for (int i = 0; i < ask_cnt; i++) {
        // 把深度足够的终止节点子树加进树状数组
        while (ptr < term_cnt && node[terminal_nodes[ptr]].depth >= asks[i].need) {
            int u = terminal_nodes[ptr];
            bit_range_add(node[u].tin, node[u].tout, node[u].weight);
            ptr++;
        }
        answer[asks[i].id] += bit_query(node[asks[i].state].tin);
    }
}

// 处理一个询问：找出 [L,R] 后，把每个可能结束位置拆成一个离线子问题。
// 规则长度为 k、替换起点为 p 时，要求区间 [p, p+k-1] 覆盖 [L, R]，
// 于是 p = L - (k 的差异前缀长)，等价于统计深度阈值满足条件的终止节点个数。
// 换个更直接的说法：结束位置 i = p+k-1 必须 >= R，且 p = i-k+1 >= L，
// 所以 k >= i-L+1；每个 i >= R 对应一个子问题 (state(i), need = i-L+1)。
void process_query(int id, const string &a, const string &b) {
    // 替换不改变长度
    if (a.size() != b.size()) {
        answer[id] = 0;
        return;
    }

    int len = a.size();
    // first_diff / last_diff 即询问两串的差异区间 [L, R]
    int first_diff = -1;
    int last_diff = -1;
    for (int i = 0; i < len; i++) {
        if (a[i] != b[i]) {
            if (first_diff == -1) {
                first_diff = i;
            }
            last_diff = i;
        }
    }

    if (first_diff == -1) {
        answer[id] = 0; // 两串完全相同，题目保证 t1 != t2，必无解
        return;
    }

    // 扫描字符对串，每个结束位置 i >= R 产生一个子问题：
    // 统计 fail 祖先中深度 >= i - L + 1 的终止节点数量（深度 = 规则长度）。
    // state 始终是「T[0..i] 的最长后缀规则前缀」，fail 祖先就是所有匹配的规则。
    int state = 0;
    for (int i = 0; i < len; i++) {
        int ch = code_pair(a[i], b[i]);
        state = move_state(state, ch);
        if (i >= last_diff) {
            Ask ask;
            ask.need = i - first_diff + 1;
            ask.state = state;
            ask.id = id;
            asks.push_back(ask);
        }
    }
}

int main() {
    raise_stack_limit(); // 递归求 DFS 序可能非常深，先把系统栈上限调大
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    new_node(-1); // 先把根节点（编号 0）开出来，根没有入边字符

    // 每条规则的左右串逐位合成字符对串，插入 Trie
    string a, b;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b;
        insert_pair_string(a, b);
    }

    sort_children();      // 孩子按边字符排序，find_child 才能二分查找
    build_ac_automaton(); // BFS 求 fail 指针
    build_fail_tree();    // fail 指针反向建树（只加边）
    dfs_timer = 0;
    dfs_fail_tree(0);     // 从根开始递归求 DFS 序

    // 收集所有终止节点（即所有规则串的结尾）
    for (int i = 1; i < node_cnt; i++) {
        if (node[i].weight > 0) {
            terminal_nodes.push_back(i);
        }
    }

    answer.assign(q + 1, 0);
    asks.reserve(1000000);
    // 每个询问在线拆成若干离线子问题，扫完 Trie 后统一回答
    for (int id = 1; id <= q; id++) {
        cin >> a >> b;
        process_query(id, a, b);
    }

    answer_offline_asks();

    for (int id = 1; id <= q; id++) {
        cout << answer[id] << '\n';
    }

    return 0;
}

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-14 23:42
 * update_at: 2026-10-16 19:41
 */
// main3.cpp：map 精确分组差异核心，每组普通插入左右 Trie。
// 与 main.cpp 使用相同的分组和建树方式，计数改用 DFS 序矩形与二维扫描线。
//
// 【匹配条件】规则 s1=P+A+S、s2=P+B+S，询问 t1=X+C+Y、t2=X+D+Y。
// 规则可用 ⟺ (A,B)=(C,D)，P 是 X 的后缀，S 是 Y 的前缀。
// 组内把反转的 P、X 插入左 Trie，把正向的 S、Y 插入右 Trie。
// 规则左终点是询问左终点的祖先，且规则右终点是询问右终点的祖先，才合法。
//
// 【矩形与点】DFS 序把节点 u 的子树变成区间 [tin[u],tout[u]]。
// 规则的左右终点为 u、v，就生成矩形：
//   [tin[u],tout[u]] × [tin[v],tout[v]]。
// 询问的左右终点为 x、y，就生成点 (tin[x],tin[y])。
// 答案就是本组内覆盖询问点的规则矩形数，重复规则分别计数。
//
// 【扫描线】矩形在 x=tin[u] 时给 y 区间加 1，在 x=tout[u]+1 时减 1。
// 按 x 排序，同坐标先更新后查询；树状数组维护 y 方向的差分，单点查覆盖数。
// 时间 O((L1+L2) log(L1+L2))，空间 O(L1+L2)（固定 26 字母表）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXGROUP = 200000 + 10; // 核心组数不超过规则数 n
const int MAXNODE = 5000000 + 10; // 规则与有效询问的单侧总长度至多 5000000，另有两个根

// 普通 Trie；节点编号与 DFS 序至多 5000002，用 int 控制内存。
struct Node {
    int ch[26];
    int tin, tout; // 该节点子树的 DFS 序闭区间
};

struct Record {
    string a; // 两侧不变，只保留原串，目标串只用于找差异核心
    int l, r; // 首尾差异位置，0-based
    int left, right; // 本条记录在左右 Trie 中的终点
    int query_id; // 规则为 0，询问为原始询问编号
};

struct Event {
    int x;
    int y1, y2; // 更新区间 [y1,y2]；查询点时 y1==y2
    int value; // 更新为 +1 或 -1，查询为 0
    int query_id; // 更新为 0，查询为原始询问编号
};

Node node[MAXNODE];
vector<int> group_records[MAXGROUP]; // group_records[g]：属于第 g 个核心组的记录编号
bool has_query[MAXGROUP]; // has_query[g]：第 g 组是否包含询问
ll bit[MAXNODE]; // 右 Trie 的 DFS 序上维护差分数组
int node_cnt, group_cnt, dfs_timer, right_size;
ll n, q;
map<pair<string, string>, int> core_id;
vector<Record> records(1); // 完整记录从编号 1 开始保存
vector<Event> events; // 当前核心组的矩形更新与点查询
vector<ll> answer; // answer[id]：第 id 个询问的答案

int new_node() {
    node_cnt++;
    // 组间复用节点池，清空旧孩子和 DFS 序。
    for (int c = 0; c < 26; c++) node[node_cnt].ch[c] = 0;
    node[node_cnt].tin = node[node_cnt].tout = 0;
    return node_cnt;
}

int get_child(int u, int ch) {
    if (node[u].ch[ch] == 0) node[u].ch[ch] = new_node();
    return node[u].ch[ch];
}

// 与主解相同：按差异核心分组，保存规则与有效询问。
void read_record(int query_id) {
    string a, b;
    cin >> a >> b;
    if (a.size() != b.size()) return;
    int l = -1, r = -1;
    ll len = a.size();
    for (ll i = 0; i < len; i++) {
        if (a[i] != b[i]) {
            if (l == -1) l = i;
            r = i;
        }
    }
    if (l == -1) return; // 恒等规则不能得到题目要求的不同目标串

    pair<string, string> key(a.substr(l, r - l + 1), b.substr(l, r - l + 1));
    auto it = core_id.find(key);
    int g;
    if (it == core_id.end()) {
        if (query_id != 0) return; // 规则中没有这个核心，询问答案为 0
        g = ++group_cnt;
        core_id[key] = g;
    } else {
        g = it->second;
    }
    if (query_id != 0) has_query[g] = true;

    Record current;
    current.a = move(a);
    current.l = l;
    current.r = r;
    current.left = current.right = 0;
    current.query_id = query_id;
    records.push_back(move(current));
    int record_id = records.size() - 1;
    group_records[g].push_back(record_id);
}

// 与主解相同：规则和询问一起插入，左侧反转、右侧正向，空侧对应根。
// 矩形计数需要同时记住每条记录的左右终点。
void build_group(int g, int left_root, int right_root) {
    for (auto record_id : group_records[g]) {
        int u = left_root;
        for (ll i = records[record_id].l - 1; i >= 0; i--) {
            u = get_child(u, records[record_id].a[i] - 'a');
        }
        records[record_id].left = u;

        u = right_root;
        ll len = records[record_id].a.size();
        for (ll i = records[record_id].r + 1; i < len; i++) {
            u = get_child(u, records[record_id].a[i] - 'a');
        }
        records[record_id].right = u;
    }
}

// 进入时编号，访问完所有孩子后记录子树右端点。
void dfs_order(int u) {
    node[u].tin = ++dfs_timer;
    for (int c = 0; c < 26; c++) {
        int v = node[u].ch[c];
        if (v != 0) dfs_order(v);
    }
    node[u].tout = dfs_timer;
}

// 每条规则生成矩形的两个更新事件，每个询问生成一个点查询。
void make_events(int g) {
    events.clear();
    for (auto record_id : group_records[g]) {
        int u = records[record_id].left;
        int v = records[record_id].right;
        Event event;
        event.x = node[u].tin;
        event.y1 = node[v].tin;
        event.y2 = node[v].tout;
        event.value = 1;
        event.query_id = records[record_id].query_id;
        if (event.query_id == 0) {
            events.push_back(event); // x=tin[u]，矩形开始覆盖
            event.x = node[u].tout + 1;
            event.value = -1;
            events.push_back(event); // x=tout[u]+1，矩形结束覆盖
        } else {
            event.y2 = event.y1;
            event.value = 0;
            events.push_back(event);
        }
    }
}

// 同一横坐标先处理全部更新，再回答询问，保证矩形边界是闭区间。
bool cmp_event(const Event &a, const Event &b) {
    if (a.x != b.x) return a.x < b.x;
    return a.query_id < b.query_id;
}

void bit_add(int pos, ll value) {
    for (; pos <= right_size; pos += pos & -pos) bit[pos] += value;
}

ll bit_query(int pos) {
    ll result = 0;
    for (; pos > 0; pos -= pos & -pos) result += bit[pos];
    return result;
}

// 差分数组在左端加、右端后一位减，前缀和就是该位置的覆盖数。
void bit_range_add(int l, int r, ll value) {
    bit_add(l, value);
    bit_add(r + 1, -value);
}

void solve_events() {
    // 每组只清空本组右 Trie 用到的坐标，互不影响，总清理量受总长度控制。
    fill(bit + 1, bit + right_size + 1, 0);
    sort(events.begin(), events.end(), cmp_event);
    for (const auto &event : events) {
        if (event.query_id == 0) {
            bit_range_add(event.y1, event.y2, event.value);
        } else {
            answer[event.query_id] = bit_query(event.y1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    records.reserve(n + q + 1);
    events.reserve(2 * n + q);
    answer.assign(q + 1, 0);
    for (ll i = 1; i <= n; i++) read_record(0);
    for (ll i = 1; i <= q; i++) read_record(i);
    core_id.clear();

    for (int g = 1; g <= group_cnt; g++) {
        if (!has_query[g]) continue;
        node_cnt = 0;
        int left_root = new_node();
        int right_root = new_node();
        build_group(g, left_root, right_root);

        // 两棵树分别从 1 编号，构成独立的横、纵坐标。
        dfs_timer = 0;
        dfs_order(left_root);
        dfs_timer = 0;
        dfs_order(right_root);
        right_size = dfs_timer;
        make_events(g);
        solve_events();
    }
    for (ll i = 1; i <= q; i++) cout << answer[i] << '\n';
    return 0;
}

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-15 00:29
 * update_at: 2026-10-15 11:26
 */
// main4.cpp：差异核心离线分桶 + 每组左右 Trie + DFS 激活与祖先链求和。
// 总时间 O(L1+L2)，确定性；核心、左右侧都按下一个字符离线分组建树。
//
// ==================== 教学导读 ====================
// 【和 main.cpp 的关系】计数部分完全一样（前后缀分解 → 左 Trie DFS 激活 →
// 右 Trie 祖先链求和），差别只在「建树和分组」：main.cpp 用 map 比字符串分组、
// 用逐字符查孩子建 Trie，代价里带 log；本解把这两处都换成「离线分桶」，做到严格线性。
//
// 【离线分桶建 Trie】一次性拿到一批要插入的串，不用逐个从根往下找孩子：
// 在每个节点处，把所有经过这里的串按「下一个字符」分桶（26 或 676 个桶），
// 每个非空桶就是一个新孩子。这样每个字符只被读常数次，建树总代价 O(总长)。
// 串走到头（next_char 返回 -1）时，记录就挂在当前节点上——
// 相同的串必然挂在同一个终点，所以「终点上的记录链表」就是精确分组，不需要 map。
//
// 【三种建树模式】同一个 build_trie 用 mode 参数复用：
//   CORE：按差异核心的字符对 (a[pos], b[pos]) 建树，终点链表就是核心组；
//   LEFT：按核心左边那段的反转（从核心向左走）建树，终点链表挂规则/询问；
//   RIGHT：按核心右边那段正向建树，只记终点编号。
// 每个核心组复用全局节点池（node_cnt 归零重建），内存与单组规模无关。
//
// 【计数为什么线性】每条规则只在左 Trie 终点上挂一次、激活撤销各一次；
// 每个询问沿右 Trie 祖先链求和，所有询问的链长之和受右 Trie 总长 L2 限制。
// 总复杂度 O(L1+L2)，不依赖字母表大小的乘法因子（桶是 O(1) 分发）。
//
// 【细节坑】全局 bucket 数组只在当前节点用过、且用完立刻清空，
// 所以父节点处理孩子之前必须先把所有桶收走（见 build_trie 末尾）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXNODE = 5000000 + 10; // 有效输入单侧总长度至多 5000000，另有两个根
const int SIGMA = 26 * 26;
const int CORE = 0, LEFT = 1, RIGHT = 2;

// 一个有效规则或询问；保留原串，通过 l/r 访问三段，不复制子串。
struct Item {
    string a, b;
    int l, r;
    int next;      // 离线分桶时的临时链表；核心建完后连接同核心的记录
    int left_next; // 挂在左 Trie 终点的记录链表，不受右 Trie 建树影响
    int right;     // 右 Trie 的终点
    int id;        // 规则为 0，询问为原编号
};

// 节点编号、记录数不超过 5000002，用 int 控制大数组内存。
struct Node {
    int child, sibling, parent;
    int items;  // 核心树或左 Trie 的终点记录链表
    int weight; // 右 Trie 上当前激活的规则数量，最多 n
};

struct Bucket {
    int head; // 下一字符相同的记录链表，0 表示空桶
};

struct Work {
    int u, head, depth; // 在 u 处理这一批记录，当前字符下标为 depth
};

Node node[MAXNODE];
Bucket bucket[SIGMA]; // 全过程共用，初始化一次，只清空实际使用的桶
vector<Item> item;
vector<Work> work;
vector<int> used, groups, members;
vector<ll> answer;
ll n, q;
int node_cnt;

// 节点池先用于核心树，然后每个核心组复用；只初始化实际新建的节点。
int new_node(int parent) {
    node_cnt++;
    node[node_cnt].child = node[node_cnt].sibling = 0;
    node[node_cnt].parent = parent;
    node[node_cnt].items = node[node_cnt].weight = 0;
    return node_cnt;
}

// 读入规则或询问，长度不同、无变化的记录不参与建树。
void read_item(int query_id, int &head) {
    Item current;
    cin >> current.a >> current.b;
    if (current.a.size() != current.b.size()) return;
    current.l = current.r = -1;
    ll len = current.a.size();
    for (ll i = 0; i < len; i++) {
        if (current.a[i] != current.b[i]) {
            if (current.l == -1) current.l = i;
            current.r = i;
        }
    }
    if (current.l == -1) return;
    current.next = head;
    current.left_next = current.right = 0;
    current.id = query_id;
    item.push_back(move(current));
    head = item.size() - 1;
}

// 按建树模式读下一个字符；-1 表示串已结束。
// 核心读取字符对（保证 (A,B) 逐位一致），左侧反转读取，右侧正向读取。
// depth 是「已经匹配的字符个数」，三种模式共用同一个分桶循环。
int next_char(int id, int depth, int mode) {
    const Item &s = item[id];
    if (mode == CORE) {
        if (depth > s.r - s.l) return -1;
        int pos = s.l + depth;
        return (s.a[pos] - 'a') * 26 + s.b[pos] - 'a';
    }
    if (mode == LEFT) {
        if (depth >= s.l) return -1;
        return s.a[s.l - 1 - depth] - 'a';
    }
    ll pos = s.r + 1 + depth;
    ll len = s.a.size();
    if (pos >= len) return -1;
    return s.a[pos] - 'a';
}

// 离线建 Trie：每个节点把经过这里的记录按下一字符分桶。
// work 是显式任务栈，串再长也不使用递归；孩子不需要保存边字符（字符就是桶号）。
// 串走到头时：CORE/LEFT 模式把记录挂到当前节点的 items 链表上（终点即分组），
// RIGHT 模式只把终点编号写回 item[id].right。
void build_trie(int root, int head, int mode) {
    work.clear();
    work.push_back({root, head, 0});
    while (!work.empty()) {
        Work current = work.back();
        work.pop_back();
        used.clear();
        for (int id = current.head; id != 0; ) {
            int next = item[id].next; // 改链表前保存原来的下一条记录
            int ch = next_char(id, current.depth, mode);
            if (ch == -1) {
                if (mode == CORE) {
                    item[id].next = node[current.u].items;
                    node[current.u].items = id;
                } else if (mode == LEFT) {
                    item[id].left_next = node[current.u].items;
                    node[current.u].items = id;
                } else {
                    item[id].right = current.u;
                }
            } else {
                if (bucket[ch].head == 0) used.push_back(ch);
                item[id].next = bucket[ch].head;
                bucket[ch].head = id;
            }
            id = next;
        }
        // CORE 模式：终点上挂满记录，就是一个完整的差异核心组，交给 solve_groups。
        if (mode == CORE && node[current.u].items != 0) {
            groups.push_back(node[current.u].items);
        }
        // 必须先取走并清空本节点的所有桶，再处理任何孩子，才能复用全局桶。
        for (size_t i = 0; i < used.size(); i++) {
            int ch = used[i];
            int v = new_node(current.u);
            node[v].sibling = node[current.u].child;
            node[current.u].child = v;
            work.push_back({v, bucket[ch].head, current.depth + 1});
            bucket[ch].head = 0;
        }
    }
}

// 根据本核心组的记录编号，重建临时链表；左右建树分别调用一次。
int make_list() {
    int head = 0;
    for (size_t i = 0; i < members.size(); i++) {
        int id = members[i];
        item[id].next = head;
        head = id;
    }
    return head;
}

// 进入左 Trie 的节点：先激活全部规则，再回答同节点的全部询问。
// 「激活」= 在右 Trie 的规则终点 weight +1，表示这条规则当前可用。
void enter_node(int u) {
    for (int id = node[u].items; id != 0; id = item[id].left_next) {
        if (item[id].id == 0) node[item[id].right].weight++;
    }
    for (int id = node[u].items; id != 0; id = item[id].left_next) {
        if (item[id].id != 0) {
            ll result = 0;
            // 暴力沿右 Trie 的祖先链求和；所有询问的链长之和受 L2 限制。
            // 被统计到的规则：左端已被 DFS 路径保证「P 是 X 的后缀」，
            // 右端是 v 的祖先保证「S 是 Y 的前缀」，两个条件都恰好满足。
            for (int v = item[id].right; v != 0; v = node[v].parent) {
                result += node[v].weight;
            }
            answer[item[id].id] = result;
        }
    }
}

// 离开左 Trie 的节点：撤销这里的规则，避免影响其他分支。
void leave_node(int u) {
    for (int id = node[u].items; id != 0; id = item[id].left_next) {
        if (item[id].id == 0) node[item[id].right].weight--;
    }
}

// 用 child / sibling / parent 模拟 DFS，不开递归栈或额外长链栈。
// 进入 = 激活当前节点上的规则，离开 = 撤销，保证兄弟分支不互相干扰。
void dfs_left(int root) {
    int u = root;
    while (u != 0) {
        enter_node(u);
        if (node[u].child != 0) {
            u = node[u].child;
            continue;
        }
        while (u != 0) {
            leave_node(u);
            if (node[u].sibling != 0) {
                u = node[u].sibling;
                break;
            }
            u = node[u].parent;
        }
    }
}

void solve_groups() {
    for (size_t g = 0; g < groups.size(); g++) {
        members.clear();
        bool has_rule = false, has_query = false;
        for (int id = groups[g]; id != 0; id = item[id].next) {
            members.push_back(id);
            if (item[id].id == 0) has_rule = true;
            else has_query = true;
        }
        if (!has_rule || !has_query) continue;

        // groups 保存的是记录链表头，不是核心树节点，因此可以安全复用节点池。
        node_cnt = 0;
        int left_root = new_node(0);
        int right_root = new_node(0);
        build_trie(left_root, make_list(), LEFT);
        build_trie(right_root, make_list(), RIGHT);
        dfs_left(left_root);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    item.reserve(n + q + 1);
    item.resize(1); // 记录编号从 1 开始，0 是链表结束标记
    answer.assign(q + 1, 0);
    int head = 0;
    for (ll i = 1; i <= n; i++) read_item(0, head);
    for (ll i = 1; i <= q; i++) read_item(i, head);
    int core_root = new_node(0);
    build_trie(core_root, head, CORE);
    solve_groups();
    for (ll i = 1; i <= q; i++) cout << answer[i] << '\n';
    return 0;
}