[蓝桥杯]密文搜索

密文搜索

题目描述

福尔摩斯从 X 星收到一份资料，全部是小写字母组成。

他的助手提供了另一份资料：许多长度为 8 的密码列表。

福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。

请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。

输入描述

输入第一行：一个字符串 ss，全部由小写字母组成，长度小于 1024*1024。

紧接着一行是一个整数 nn,表示以下有 nn 行密码，1≤n≤10001≤n≤1000。

紧接着是 nn 行字符串，都是小写字母组成，长度都为 8。

输出描述

输出一个整数, 表示每行密码的所有排列在 ss 中匹配次数的总和。

输入输出样例

示例

输入

aaaabbbbaabbcccc
2
aaaabbbb
abcabccc

输出

运行限制

最大运行时间：3s
最大运行内存: 512M

总通过次数: 821 | 总提交次数: 975 | 通过率: 84.2%

难度: 困难标签: 2015, 国赛

算法思路：滑动窗口 + 频率哈希

本问题要求在长字符串中高效搜索多个长度为8的密码的所有排列出现的总次数。核心挑战在于避免枚举所有排列组合（8! = 40320），采用字符频率统计+滑动窗口优化策略：

图片

代码

graph TD A[输入主串s和密码列表] --> B[密码预处理] B --> C[频率向量→字符串<br>存入哈希表] C --> D[初始化窗口0-7] D --> E[更新频率字符串<br>查询哈希表] E --> F[滑动窗口：移左字符+移右字符] F --> G[更新两个字符频率] G --> E E --> H[累加匹配次数] H --> I[输出总和]

输入主串s和密码列表

密码预处理

频率向量→字符串
存入哈希表

初始化窗口0-7

更新频率字符串
查询哈希表

滑动窗口：移左字符+移右字符

更新两个字符频率

累加匹配次数

输出总和

算法步骤

频率向量表示排列：两个字符串互为排列当且仅当字符频率相同。将每个密码表示为26维频率向量（a~z的计数）。
密码预处理：计算每个密码的频率向量，转换为26字符的字符串（如 "400400..."），存入哈希表记录出现次数。
滑动窗口扫描：
- 初始化窗口（0~7）的频率向量
- 窗口右移时，仅更新移出字符（左边界）和移入字符（右边界）的频率
- 实时更新频率字符串，查询哈希表累加匹配次数
优化关键：维护动态频率字符串，避免每次重新生成。
算法思路：滑动窗口 + 频率哈希

本问题要求在长字符串中高效搜索多个长度为8的密码的所有排列出现的总次数。核心挑战在于避免枚举所有排列组合（8! = 40320），采用字符频率统计+滑动窗口优化策略：
频率向量表示排列：两个字符串互为排列当且仅当字符频率相同。将每个密码表示为26维频率向量（a~z的计数）。
密码预处理：计算每个密码的频率向量，转换为26字符的字符串（如 "400400..."），存入哈希表记录出现次数。
滑动窗口扫描：
- 初始化窗口（0~7）的频率向量
- 窗口右移时，仅更新移出字符（左边界）和移入字符（右边界）的频率
- 实时更新频率字符串，查询哈希表累加匹配次数
优化关键：维护动态频率字符串，避免每次重新生成。
密码预处理（O(n×26)）
- 对每个密码，统计a~z频率（26维数组）
- 频率数组转为26字符字符串（如 [4,4,0,...] → "440..."）
- 哈希表记录频率字符串出现次数
窗口初始化（O(26)）
- 计算主串前8字符的频率数组
- 生成初始频率字符串
滑动窗口（O(|s|×2)）
- 移出左边界字符：对应频率减1，更新频率字符串
- 移入右边界字符：对应频率加1，更新频率字符串
- 查询哈希表累加匹配次数
结果输出：总匹配次数

算法步骤

密码预处理（O(n×26)）
- 对每个密码，统计a~z频率（26维数组）
- 频率数组转为26字符字符串（如 [4,4,0,...] → "440..."）
- 哈希表记录频率字符串出现次数
窗口初始化（O(26)）
- 计算主串前8字符的频率数组
- 生成初始频率字符串
滑动窗口（O(|s|×2)）
- 移出左边界字符：对应频率减1，更新频率字符串
- 移入右边界字符：对应频率加1，更新频率字符串
- 查询哈希表累加匹配次数
结果输出：总匹配次数

代码实现（C++）

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(0);string s;cin >> s;int n;cin >> n;// 1. 密码预处理：频率数组→字符串unordered_map<string, int> count_map;for (int i = 0; i < n; i++) {string pwd;cin >> pwd;vector<int> freq(26, 0);for (char c : pwd) freq[c - 'a']++;string key(26, '0');for (int j = 0; j < 26; j++) key[j] = '0' + freq[j]; // 频率转字符count_map[key]++;}// 2. 处理边界：主串长度不足8int len = s.size();if (len < 8) {cout << 0 << endl;return 0;}// 3. 初始化窗口频率vector<int> win_freq(26, 0);string win_key(26, '0');for (int i = 0; i < 8; i++) {int idx = s[i] - 'a';win_freq[idx]++;win_key[idx] = '0' + win_freq[idx]; // 动态更新}// 4. 滑动窗口扫描long long total = count_map[win_key]; // 初始窗口匹配for (int i = 1; i <= len - 8; i++) {// 移出左边界字符int idx_out = s[i-1] - 'a';win_freq[idx_out]--;win_key[idx_out] = '0' + win_freq[idx_out];// 移入右边界字符int idx_in = s[i+7] - 'a';win_freq[idx_in]++;win_key[idx_in] = '0' + win_freq[idx_in];total += count_map[win_key]; // 查询累加}cout << total << endl;return 0;
}

代码解析

密码预处理（L15-25）
- freq[26]：存储a~z频率（freq[0]=a）
- key：26字符字符串（key[0]='4'表示a出现4次）
- count_map：记录频率字符串出现次数
窗口初始化（L35-41）
- win_freq：窗口频率数组
- win_key：动态更新的频率字符串
滑动窗口（L44-57）
- 移出字符：左边界s[i-1]频率减1，更新win_key对应位置
- 移入字符：右边界s[i+7]频率加1，更新win_key对应位置
- 查询累加：直接访问count_map
复杂度分析
- 时间：O(n×26 + |s|×2) ≈ O(26,000 + 2,000,000) = 2.03e6（1e6主串）
- 空间：O(n×26) ≈ 26,000（1000密码）

实例验证

输入：

aaaabbbbaabbcccc
2
aaaabbbb    → 频率字符：'4','4','0',...（24个0）
abcabccc    → 频率字符：'2','2','4','0',...（23个0）

执行过程：

窗口位置	子串	频率字符串	匹配密码	累加值
0-7	aaaabbbb	44000...	密码1	1
1-8	aaabbbba	44000...	密码1	2
2-9	aabbbbaa	44000...	密码1	3
8-15	aabbcccc	22400...	密码2	4

输出：4 ✓

注意事项

边界处理：
- 主串长度 <8 时直接返回0
- 窗口右边界 i+7 需满足 i ≤ len-8
频率转换：
- 密码字符必须小写（c-'a'索引0~25）
- 频率范围0~8（'0'+freq 不会溢出）
哈希冲突：
- 不同频率数组可能生成相同字符串（概率极低）
- 可改用vector作为键（需自定义哈希）

多方位测试点

测试类型	输入样例	预期输出	验证要点
主串不足8字符	"abc", 1, "abcdefgh"	0	边界处理
单密码全匹配	"aaaaaaaa", 1, "aaaaaaaa"	9	重叠窗口计数
多密码相同频率	两密码频率相同	双倍计数	哈希表累计验证
零匹配	"abcdefgh", 1, "zzzzzzzz"	0	无匹配处理
最大规模	1e6长度主串, 1000密码	约1e6次操作	时间效率（<0.5s）
特殊字符分布	"abcdabcd", 1, "aabbccdd"	1	频率计算正确性

优化建议

向量哈希替代字符串：

struct VectorHash {size_t operator()(const vector<int>& v) const {size_t seed = 0;for (int x : v) seed ^= hash<int>()(x) + 0x9e3779b9 + (seed<<6) + (seed>>2);return seed;}
};
unordered_map<vector<int>, int, VectorHash> count_map; // 避免字符串转换

并行化处理：

#pragma omp parallel for reduction(+:total)
for (int i = 0; i <= len-8; i++) {// 各窗口独立计算
}

内存优化：
- 链式前向星存储频率表（减少vector开销）
- 预分配哈希表桶数量：count_map.reserve(n)