標題：密文搜索

福爾摩斯從X星收到一份資料，全部是小寫字母組成。
他的助手提供了另一份資料：許多長度為8的密碼列表。
福爾摩斯發現，這些密碼是被打亂后隱藏在先前那份資料中的。

請你編寫一個程序，從第一份資料中搜索可能隱藏密碼的位置。要考慮密碼的所有排列可能性。

數據格式：
輸入第一行：一個字符串s，全部由小寫字母組成，長度小于1024*1024
緊接著一行是一個整數n,表示以下有n行密碼，1<=n<=1000
緊接著是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-7=3個。

（既然都要求全排列，那么也就是所有的排列方式都有可能，那實際上只需要計算各字母的個數就可以了，這里可能有點繞，仔細理解一下）

完整代碼如下：

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, j+8);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 <= i+7; 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);} }

總結

以上是生活随笔為你收集整理的蓝桥杯第六届国赛JAVA真题----密文搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。