本文主要是介绍洛谷 P8630 [蓝桥杯 2015 国 B] 密文搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
福尔摩斯从 X 星收到一份资料，全部是小写字母组成。
他的助手提供了另一份资料：许多长度为 8 的密码列表。
福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。
请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。
输入格式
输入第一行：一个字符串 s，全部由小写字母组成，长度小于 1024×1024。
紧接着一行是一个整数 n, 表示以下有 n 行密码，1≤n≤1000。
紧接着是 n 行字符串，都是小写字母组成，长度都为 8。
输出格式
一个整数，表示每行密码的所有排列在 s 中匹配次数的总和。
输入输出样例
输入 #1
aaaabbbbaabbcccc 2 aaaabbbb abcabccc
输出 #1
4
说明/提示
第一个密码匹配了 3 次，第二个密码匹配了 1 次，一共 4 次。
时限 3 秒, 512M。蓝桥杯 2015 年第六届国赛
解题思路
这题可以使用字符串哈希，因为不用考虑字符顺序，可以先统计一个字符串中每个字符出现的次数，然后使用使用进制哈希将字符串转换为数字表示，具体操作看代码；
#include<stdio.h>
#include<string.h>
char a[1100000], b[9];
long long haxi[1100000], hx[27], left = 0, right = 8;
long long base = 131, mod = 9223372036854775807, sum = 0;
long long charge()//哈希函数
{long long ans = 0;for (int i = 1; i <= 26; i++)ans = (ans * base + hx[i]) % mod;return ans;
}
int main()
{int i, j, n;scanf("%s", a);//输入字符串int k = strlen(a);for (j = 0; j <= 7; j++)hx[a[j] - 'a' + 1]++;haxi[0] = charge();while (right < k)//k个字符字符可以从左到右组成k-7个字符串转换为的数字{hx[a[right] - 'a' + 1]++;hx[a[left] - 'a' + 1]--;left++; right++;haxi[left] = charge();}scanf("%d", &n);while (n--){scanf("%s", b);for (i = 1; i <= 26; i++)//初始化hx[i] = 0;for (i = 0; i <= 7; i++)hx[b[i] - 'a' + 1]++;long long ss = charge();for (i = 0; i <= k - 8; i++)//统计数量if (ss == haxi[i])sum++;}printf("%lld", sum);return 0;
}
这篇关于洛谷 P8630 [蓝桥杯 2015 国 B] 密文搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
