空壳网站查询,门户网站建设存在问题与不足,企业网站制作的公司,wap建站系统开源题目描述
福尔摩斯从 X 星收到一份资料#xff0c;全部是小写字母组成。
他的助手提供了另一份资料#xff1a;许多长度为 8 的密码列表。
福尔摩斯发现#xff0c;这些密码是被打乱后隐藏在先前那份资料中的。
请你编写一个程序#xff0c;从第一份资料中搜索可能隐藏…题目描述
福尔摩斯从 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 年第六届国赛 解题思路
这题可以使用字符串哈希因为不用考虑字符顺序可以先统计一个字符串中每个字符出现的次数然后使用使用进制哈希将字符串转换为数字表示具体操作看代码
#includestdio.h
#includestring.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;
}
