跨境电商入门基础知识,廊坊网站优化,公司注册商标的流程及资料,茶叶网站模板下载标题#xff1a;密文搜索福尔摩斯从X星收到一份资料#xff0c;全部是小写字母组成。
他的助手提供了另一份资料#xff1a;许多长度为8的密码列表。
福尔摩斯发现#xff0c;这些密码是被打乱后隐藏在先前那份资料中的。请你编写一个程序#xff0c;从第一份资料中搜索可…标题密文搜索福尔摩斯从X星收到一份资料全部是小写字母组成。
他的助手提供了另一份资料许多长度为8的密码列表。
福尔摩斯发现这些密码是被打乱后隐藏在先前那份资料中的。请你编写一个程序从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。数据格式
输入第一行一个字符串s全部由小写字母组成长度小于1024*1024
紧接着一行是一个整数n,表示以下有n行密码1n1000
紧接着是n行字符串都是小写字母组成长度都为8要求输出
一个整数, 表示每行密码的所有排列在s中匹配次数的总和。例如
用户输入
aaaabbbbaabbcccc
2
aaaabbbb
abcabccc则程序应该输出
4这是因为第一个密码匹配了3次第二个密码匹配了1次一共4次。资源约定
峰值内存消耗含虚拟机 512M
CPU消耗 5000ms
请严格按要求输出不要画蛇添足地打印类似“请您输入...” 的多余内容。所有代码放在同一个源文件中调试通过后拷贝提交该源码。
注意不要使用package语句。不要使用jdk1.7及以上版本的特性。注意主类的名字必须是Main否则按无效代码处理。思路根据题意我们一开始的思路是求解每行密码c的所有排列方式然后与总的密文s进行逐个比较记录匹配成功的次数。
而这个题目的巧妙之处在于正因为需要求每行密码的所有排列在s中匹配次数的总和所以我们可以直接统计每行密码中所包含各字母的个数与长度为8的s子区间的各字母的个数进行比较。而且由于密码c的长度固定为8所以我们只需在s中截取长度为8的区间进行比较即可。而s中这样的区间刚好有s.length()-7个。
例如: 1 2 3 4 5 6 7 8 9 10 s长度为10
则长度为8的区间只有1-8 2-9 3-10一共是10-73个。
既然都要求全排列那么也就是所有的排列方式都有可能那实际上只需要计算各字母的个数就可以了这里可能有点绕仔细理解一下
完整代码如下
import java.util.Scanner;public class Main {static Scanner in new Scanner(System.in);static String s;static String[] c new String[1000];static int n;static int cnt 0;public static void main(String[] args) {s in.next();n in.nextInt();for (int i 1; i n; i) {String c in.next();String x sum(c);for (int j 0; j s.length()-7; j) {String con s.substring(j, j8);if (x.equals(sum(con))) {cnt;}}}System.out.println(cnt);}/*** sum(String)函数用来求子串中的各字母个数返回一个String* 思路采用桶排序的排序方式在记录下每个字母出现的次数时这里注意由于比较的是字母对应数组下标的的话是数字要进行类似c.charAt(i)-a* 最后传出String方便比较将int[]转换成String* */private static String sum(String c) {String result ;int[] sum new int[26];for (int i 0; i c.length()-1; i) {int index c.charAt(i)-a;sum[index]1;}/*** int[]-String* */for (int i 0; i sum.length; i) {result sum[i] ;}return result;}
}
下面这种做法是借鉴的网上的基本思路基本相同区别在于下面这种方法是最后比较的是int[]而非String代码量不如博主的少。在比赛中尽量避免繁琐的思路代码越精简越好。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n;String str new String();String s new String();int[][] a new int[1005][26];int[] b new int[26];str in.next();for (int i 0; i str.length()-7; i) {for (int j i; j i7; j) {a[i][str.charAt(j)- a] 1;}}n in.nextInt();int sum 0;for (int k 0; k n; k) {int flag 0;for (int i 0; i b.length; i) {b[i] 0;}s in.next();for (int i 0; i s.length(); i) {b[s.charAt(i) - a] 1;}for (int i 0; i str.length()-7; i) {flag 1;for (int j 0; j 26; j) {if (a[i][j] ! b[j]) {flag 0;break;}}if (flag 1) {sum;}}}System.out.println(sum);}
}
