题解：P13718 [GCPC 2024] Copycat Catcher¶
题目传送门 P13718 [GCPC 2024] Copycat Catcher
题目概述¶
给定一个 参考程序 以及若干 查询程序。对于每个查询程序，判断是否存在参考程序的一个 连续子序列，使得在把查询程序中的变量统一地重命名（相同变量映射到同一个新变量，不同变量映射到不同新变量）后，能够得到该子序列，若能则输出 yes，否则输出 no。
具体来说，我们对 程序 作如下定义：
-
一个程序由若干 token 组成，且 token 仅由英文字母、数字、
(、)组成，token 之间用空格分隔。 -
由单独一个英文字母构成的 token 称为 变量，其余 token 称为 常量。
思路概述¶
不难发现，token 具体的内容对匹配而言是无意义的，所以我们可以把 token 名抽象掉，将它们使用一个 id 进行替换。
具体来说：
-
对于 常量：直接对常量进行 hash，用得到的 hash 值作为这个 token 的 id；为了避免碰撞也可以使用一个
unordered_map<string, int>维护一个自增的 id。 -
对于 变量：在当前序列（参考程序的子段或查询程序）中，记录该变量第一次出现的相对下标
firstPos（相对与左边界），以后出现该变量时使用同一个firstPos代替。
为了避免二者的冲突，我们可以在哈希值的最低位作区分（变量 → 1，常量 → 0），这样便不存在冲突。
这样，我们就将 token 转化为了数字，接下来的就可以当做是字符串匹配。
因为这里是给定多个模式串和一个待匹配串，所以使用 滚动哈希（多项式哈希）进行匹配：
先枚举参考程序的所有 \([l,r]\) 区间，计算得到所有区间的其哈希值 curHash，然后将得到的哈希值按照区间长度 \(len=r-l+1\) 放入 hashesByLen[len]。
随后对每一种长度 \(len\)，对对应的数组进行排序，这样可以方便后续的查找。
查询时：
- 按同样的方式把查询程序映射为哈希值
qryHash。 - 若查询长度 \(m \le n\)，在
hashesByLen[m]中二分查找qryHash，存在则答案为yes，否则为no。
正确性证明(AI Support)¶
我们分别证明三件事：
Lem. 1¶
对任意 token 序列 \(S\)（可以是参考程序的子段或查询程序），上述映射得到的整数序列 \(T(S)\) 与“变量统一重命名” 的含义是完全等价的。
证明如下：
-
对常量：所有出现相同的常量得到相同的 id，不同常量得到不同的 id，显然保持了常量的相等关系。
-
对变量：设变量 \(x\) 在 \(S\) 中第一次出现位置为 \(p\)，我们记 \(firstPos_{x}=p\)。之后 \(x\) 的每一次出现都映射为相同的 \(p\)。
-
同一变量的所有出现映射到同一个数 → 满足“同一个变量重命名为同一个新变量”。
-
不同变量的第一次出现位置必然不同（因为下标唯一），于是它们映射的数也不同 → 满足“不同变量不能映射到同一个新变量”。
Q.E.D.
Lem. 2¶
若两个序列 \(A,B\) 的映射序列相同（即 \(T(A)=T(B)\)），则 \(A\) 在变量重命名后能够得到 \(B\)，反之亦然。
证明如下：
由 Lem. 1，映射只保留了 token 之间的相等关系（常量相等、变量相等），而不关心具体的变量名。
如果 \(T(A)=T(B)\)，则两序列在所有位置上对应的 token 要么同为同一常量，要么同为同一变量（第一次出现位置相同），于是把 \(A\) 中的每个变量改名为对应的 \(B\) 中变量即可得到 \(B\)。
逆向同理。
Q.E.D.
Lem. 3¶
参考程序的任意连续子段 \(S\) 与查询程序 \(Q\) 在变量重命名意义上相等 iff
\(\text{hash}(T(S)) = \text{hash}(T(Q)),\)
其中 hash 为使用基数 \(BASE\) 的多项式滚动哈希。
Q.E.D.
证明如下：
因为映射得到的整数序列唯一确定（Lem. 1），而多项式哈希在相同基数下对相同整数序列必产生相同的哈希值。
另一方面，若两序列不同，则它们的整数序列必有第一处不同的元素 \(v \neq w\)，于是对应的多项式系数不同，整体哈希值不同（\(BASE\) 为奇数且大于 \(1\)，故不存在冲突）。
定理¶
算法对每个查询输出 yes 当且仅当查询程序能够通过变量一致性重命名变为参考程序的某个连续子段。
证明如下：
-
充分性：若算法在对应长度的哈希集合中找到了相同的哈希值，则必存在参考程序子段 \(S\) 使得 \(\text{hash}(T(S))=\text{hash}(T(Q))\)。由 Lem. 3 得到 \(T(S)=T(Q)\)，再由 Lem. 2 可知 \(Q\) 在变量重命名后可得到 \(S\)，于是答案应为
yes。 -
必要性：若 \(Q\) 能经变量重命名得到参考程序的某子段 \(S\)，则 \(T(S)=T(Q)\)（Lem. 2），于是其哈希相同，算法必在该长度的集合中找到该哈希值，输出
yes。
复杂度分析¶
-
枚举所有区间：\(\displaystyle\sum_{l=0}^{n-1}(n-l)=\frac{n(n+1)}2=O(n^2)\) 次更新哈希。
-
每次更新均为 \(O(1)\)，因此总时间 \(O(n^2)\)，空间存储所有哈希值亦为 \(O(n^2)\)
-
构造查询哈希 \(O(m)\)，二分查找 \(O(\log |\text{hashesByLen}[m]|)=O(\log n)\)。总体 \(O(\sum m + q\log n)=O(n+q\log n)\)。
综上，整体时间 \(O(n^2+q\log n)\)，空间 \(O(n^2)\)。
参考实现¶
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
// 检测是否为变量
static inline bool isVar(const string &s) {return s.size() == 1 && isalpha(s[0]);}
// 映射字符的ASCII到0-51 方便后续操作
static inline int varIdx(char c) {
if ('a' <= c && c <= 'z') return c - 'a';
return 26 + (c - 'A');
}
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr); // 输入输出优化
int n;cin>>n;
vector<string> ref(n);
for (int i = 0; i < n; ++i) cin >> ref[i]; // 读取标程
unordered_map<string, u64> constId; // 创建HashMap用于存储常量的ID
constId.reserve(4005); // 预申请空间
const u64 BASE = 0x9e3779b97f4a7c15ULL | 1ULL; // hash基数
vector<vector<u64>> hashesByLen(n + 1);
for (int l = 0; l < n; ++l) {
int firstPos[52]; // firstPos[i]记录变量i第一次出现的下标 初始化为-1
memset(firstPos, -1, sizeof firstPos);
u64 curHash = 0;
for (int r = l; r < n; ++r) { // 枚举标程的区间[l, r]
const string &tok = ref[r];
u64 value;
if (isVar(tok)) { // 当前token是变量
int idx = varIdx(tok[0]); // 将字符转为0-51
if (firstPos[idx] == -1) firstPos[idx] = r - l; // 若之前没有出现过 更新第一次出现的下标（较l而言）
int fp = firstPos[idx]; // 使用第一次出现的下标替代变量名进行hash 这样不同的变量名都可以被统一
value = ( ((fp+1) << 1) | 1ULL ); // 使用最低位区分变量和常量避免冲突 1：变量 0：常量
} else { // 当前token是常量
u64 id;
auto it = constId.find(tok); // 查找是否出现过
if (it == constId.end()) { // 没出现过 分配新ID并加入列表
id = constId.size() + 1;
constId.emplace(tok, id);
} else id = it->second; // 出现过 直接使用原有ID
value = (id << 1);// 同上 使用最低位区分变量和常量避免冲突 1：变量 0：常量
}
curHash = curHash * BASE + value; // 滚动哈希
int len = r - l + 1; // 区间长度
hashesByLen[len].push_back(curHash); // 通过长度划分
}
}
for (int len = 1; len <= n; ++len) { // 排序构造单调性
auto &vec = hashesByLen[len];
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
int q;
cin >> q;
while (q--) {// 同上 此处不作介绍
int m;
cin >> m;
vector<string> qry(m);
for (int i = 0; i < m; ++i) cin >> qry[i];
array<int, 52> firstPos;
firstPos.fill(-1);
u64 curHash = 0;
for (int i = 0; i < m; ++i) {
const string &tok = qry[i];
u64 value;
if (isVar(tok)) {
int idx = varIdx(tok[0]);
if (firstPos[idx] == -1) firstPos[idx] = i;
int fp = firstPos[idx];
value = ( (static_cast<u64>(fp + 1) << 1) | 1ULL );
} else {
u64 id;
auto it = constId.find(tok);
if (it == constId.end()) {
id = constId.size() + 1;
constId.emplace(tok, id);
} else id = it->second;
value = (id << 1);
}
curHash = curHash * BASE + value;
}
bool ok = false;
if (m <= n) { // 长度特判
const auto &vec = hashesByLen[m];
ok = binary_search(vec.begin(), vec.end(), curHash); // 二分查找
}
cout << (ok ? "yes\n" : "no\n");
}
return 0;
}