密文搜索

标题:密文搜索

福尔摩斯从X星收到一份资料,全部是小写字母组成。
他的助手提供了另一份资料:许多长度为8的密码列表。
福尔摩斯发现,这些密码是被打乱后隐藏在先前那份资料中的。

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

数据格式:

输入第一行:一个字符串s,全部由小写字母组成,长度小于1024*1024
紧接着一行是一个整数n,表示以下有n行密码,1<=n<=1000
紧接着是n行字符串,都是小写字母组成,长度都为8

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

例如:
用户输入:
aaaabbbbaabbcccc
2
aaaabbbb
abcabccc

则程序应该输出:
4

这是因为:第一个密码匹配了3次,第二个密码匹配了1次,一共4次。
资源约定:
峰值内存消耗 < 512M
CPU消耗 < 3000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。

思路:

对字符串s所有8个的情况(1-8,,2-9,3-10,…(n-7)-n)进行统计,将每种情况出现的次数存到map里,在输入密码时,将密码对应情况的个数读出来。

代码:

#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
map<int,string> map1;
map<string,int> map2;
string eight(string s){//将长度为8的字符串转为对应的str 
	int place=0,num=0;
	string str="00000000000000000000000000";
	for(int i=0;i<=7;i++){
		place=s.at(i)-'a';
		num=(str.at(place)-'0')+1;
		str=str.replace(place,1,map1[num]);
	}
	return str;
}
int main(){	
	map1[0]="0",map1[1]="1",map1[2]="2",map1[3]="3";
	map1[4]="4",map1[5]="5",map1[6]="6",map1[7]="7",map1[8]="8";
	string s,sp,str="00000000000000000000000000";//str用来记录各个字母出现的次数
	int n,count=0;
	int place=0,num=0;
	
	cin>>s>>n;
	str=eight(s);//对前8个进行首次特殊处理 
	map2[str]++;
	//去掉第一个,为下面的循环做准备 
	place=s.at(0)-'a';
	num=(str.at(place)-'0')-1;
	str=str.replace(place,1,map1[num]);
	//依次保存8个连续字符串所组成的情况 
	for(int i=8;i<s.length();i++){
		//读入新字母,place是字母在str中的位置,num为有几个字母 
		place=s.at(i)-'a';
		num=(str.at(place)-'0')+1;
		str=str.replace(place,1,map1[num]);//更新字母数 
		map2[str]++;//对应情况+1 
		//去掉第一个,为下次循环做准备 
		place=s.at(i-7)-'a';
		num=(str.at(place)-'0')-1;
		str=str.replace(place,1,map1[num]);
	}
	for(int i=0;i<n;i++){
		cin>>sp;
		count+=map2[eight(sp)];
	}
	printf("%d\n",count);
	return 0;
}
2016年5月12日 | 归档于 Uncategorized
标签:
本文的评论功能被关闭了.