题目分析

在 $N$ 个字符串中找出模式串，使得其他所有字符串与它的汉明距离恰好为 $K$

---

算法思路：哈希求和解法

核心观察

设模式串为 $S_p$，其他串 $S_i$ 满足：

$$\text{dist}(S_p, S_i) = K \quad \forall i \neq p$$

关键技巧

• 为每个字符串分配随机哈希值 $h_i$
• 对每个位置 $p$，统计四种字符的哈希和
• 通过哈希和关系识别模式串

---

算法步骤

1. 计算字符串哈希

vector<unsigned long long> h(n);
for(int i=0; i<n; i++) {
    h[i] = hash<string>()(s[i]);
}

2. 计算位置字符哈希和

对每个位置 $p$，计算四种字符的哈希和：

vector<array<unsigned long long, 4>> ps(m);
for(int p=0; p<m; p++) {
    ps[p] = {0,0,0,0};
    for(int i=0; i<n; i++) {
        ps[p][idx(s[i][p])] += h[i];
    }
}

3. 识别模式串

对候选串 $S_i$：

• $stc$：所有字符串在相同位置与 $S_i$ 相同的哈希和
• $mtc$：所有字符串在相同位置与 $S_i$ 不同的哈希和

满足条件：

$$mtc = K \times (总哈希和 - h_i)$$

for(int i=0; i<n; i++) {
    unsigned long long stc = 0;
    for(int p=0; p<m; p++) {
        stc += ps[p][idx(s[i][p])];
    }
    unsigned long long mtc = m * sm - stc;
    unsigned long long mk = k * (sm - h[i]);
    
    if(mtc == mk) {
        cout << i+1;
    }
}

---

正确性证明

设模式串为 $S_p$，对于任意位置：

• 如果 $S_i[p] = S_p[p]$，贡献 $h_i$ 到 $stc$
• 如果 $S_i[p] \neq S_p[p]$，贡献 $h_i$ 到 $mtc$

由于其他所有串与模式串恰好有 $K$ 个位置不同：

$$mtc = \sum_{i \neq p} K \cdot h_i = K \cdot (sm - h_p) $$

---

复杂度分析

• 时间复杂度：$O(N \cdot M)$
• 空间复杂度：$O(N + M)$
• 可行性：在 $N,M \leq 4100$ 时完全可行

---

样例验证

样例1：

• 输入字符串：ACC, CCA, ACA, AAA
• 通过哈希计算识别出第3个串为模式串
• 输出：3，与样例一致

---

算法优势

• 高效识别：利用哈希和关系快速判断
• 避免暴力：不需要 $O(N^2)$ 的成对比较
• 正确保证：基于汉明距离的数学性质

该解法通过巧妙的哈希求和关系高效识别出模式串。