P8630 [蓝桥杯 2015 国 B] 密文搜索--map、substr
P8630 [蓝桥杯 2015 国 B] 密文搜索
- 题目
- 解析
- 注意substr第二个参数是长度
- 代码
题目
解析
题意：密码是给出字符串S的乱序，我们需要找到有哪几个位置能够匹配密码，返回能在S中的匹配次数。
这里我们可以看作哈希，但是密码是字符串，常规数组显然不能满足。
于是我们得引入字典：map【让唯一的密码做：键，让出现次数作为值】
因为给出的密码是乱序，所以我们在存入map时先利用sort进行排序，然后值++。
为什么要先排序？因为只要字符的数量相同，那么密码就一定是S中的乱序
最后我们遍历S，一次截取8个长度，然后加上相应键的值，因为不是密码的值为0=没加
注意substr第二个参数是长度
string a = s.substr(i, 8);（第二个参数是长度！！！）
//substr中的第一个参数是起始位置，第二个参数是长度【与sort不同】
代码
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits> // 包含INT_MAX常量
#include <cctype>
#include <map>
using namespace std;
int n, ans;
string s;
map<string, int> mp;//字典string:为键，int：为值
int main() {
cin >> s >> n;
for (int i = 0; i < n; i++) {
string x;
cin >> x;
sort(x.begin(), x.end());
mp[x]++;
}
for (int i = 0; i < s.size() - 7; i++) {
string a = s.substr(i, 8);
//substr中的第一个参数是起始位置，第二个参数是长度【与sort不同】
sort(a.begin(), a.end());
ans += mp[a];
}
cout << ans;
return 0;
}