枚举删除的那一位，把删掉该位后相同的字符串分到同一组，每组贡献组合数。
OJ: luogu
题目 ID: P4503
难度:普及+/提高
标签:字符串哈希计数建模
日期: 2026-06-21 14:19
题意
给出 n 个长度都等于 L 的字符串，保证所有字符串互不相同。
如果两个字符串长度相同，并且恰好只有一位字符不同，就称它们是相似的。
要求统计一共有多少对相似字符串。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
int n, L, S;
string str[205];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> L >> S;
for (int i = 1; i <= n; i++) {
cin >> str[i];
}
// brute.cpp：直接枚举两两字符串，统计恰好只有一位不同的对数。
long long answer = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int diff = 0;
for (int k = 0; k < L; k++) {
if (str[i][k] != str[j][k]) {
diff++;
}
}
if (diff == 1) {
answer++;
}
}
}
cout << answer << '\n';
return 0;
}暴力做法就是枚举每一对字符串，再逐位比较它们有多少个位置不同。这个方法复杂度是 n 最大到 30000，肯定不行。
这题的关键观察是：
两个字符串恰好只有一位不同，当且仅当存在唯一一个位置
pos，删掉这两个字符串的第pos位后，剩下的字符串完全相同。
所以可以反过来枚举“删掉哪一位”。
固定一个位置 pos：
- 把每个字符串的第
pos位删掉 - 如果删掉后得到的结果相同，那么这些字符串两两之间在这个位置形成一批相似对
并且由于原串互不相同，两个字符串如果删掉某一位后相同，就只能在这一位不同，不可能有更多不同位。
因此每一对相似字符串会被统计且只会被统计一次。
这样问题就变成：
- 对每个位置
pos - 把所有“删掉第
pos位后的字符串”拿出来分组 - 设某组大小为
cnt - 这组贡献
cnt * (cnt - 1) / 2
为了快速得到“删掉一位后的字符串键值”，代码里用了前缀哈希和后缀哈希：
prefix_hash[i][j]：第i个字符串前j位的哈希suffix_hash[i][j]：第i个字符串从第j位到末尾的哈希
删除第 pos 位后的哈希就是：
- 左半部分哈希
- 拼上右半部分哈希
这样每个键值都能在
代码
cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 30005;
const int MAXL = 205;
const ull BASE = 131;
int n, L, S;
string str[MAXN];
ull power_base[MAXL];
ull prefix_hash[MAXN][MAXL];
ull suffix_hash[MAXN][MAXL];
ull keys[MAXN];
// 把题目中的 64 种字符映射成 1..64。
int value_of(char ch) {
if ('a' <= ch && ch <= 'z') return ch - 'a' + 1;
if ('A' <= ch && ch <= 'Z') return ch - 'A' + 27;
if ('0' <= ch && ch <= '9') return ch - '0' + 53;
if (ch == '_') return 63;
return 64; // '@'
}
void build_hash(int id) {
prefix_hash[id][0] = 0;
for (int i = 1; i <= L; i++) {
prefix_hash[id][i] = prefix_hash[id][i - 1] * BASE + value_of(str[id][i - 1]);
}
suffix_hash[id][L + 1] = 0;
for (int i = L; i >= 1; i--) {
suffix_hash[id][i] = suffix_hash[id][i + 1] * BASE + value_of(str[id][i - 1]);
}
}
// 返回删除第 pos 位后的哈希值，pos 使用 1-based。
ull erased_hash(int id, int pos) {
ull left = prefix_hash[id][pos - 1];
ull right = suffix_hash[id][pos + 1];
int right_len = L - pos;
return left * power_base[right_len] + right;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> L >> S;
for (int i = 1; i <= n; i++) {
cin >> str[i];
}
power_base[0] = 1;
for (int i = 1; i <= L; i++) {
power_base[i] = power_base[i - 1] * BASE;
}
for (int i = 1; i <= n; i++) {
build_hash(i);
}
long long answer = 0;
for (int pos = 1; pos <= L; pos++) {
for (int i = 1; i <= n; i++) {
keys[i] = erased_hash(i, pos);
}
sort(keys + 1, keys + n + 1);
long long len = 1;
for (int i = 2; i <= n; i++) {
if (keys[i] == keys[i - 1]) {
len++;
}
else {
answer += len * (len - 1) / 2;
len = 1;
}
}
answer += len * (len - 1) / 2;
}
cout << answer << '\n';
return 0;
}复杂度
设字符串数量为 n，长度为 L。
- 预处理所有前缀/后缀哈希：
- 枚举每个位置并排序所有键值：
总时间复杂度是
总结
这题本质上是一个很典型的“把恰好一位不同，转成删掉这一位后完全相同”的建模。
一旦模型转换完成，剩下就是：
- 快速生成删位后的表示
- 分组计数
所以重点不是比较字符串，而是换一个更容易统计的视角。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
