[藍橋杯]密文搜索

密文搜索

題目描述

福爾摩斯從 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)