結果

問題 No.430 文字列検索
ユーザー hermione17
提出日時 2016-10-03 00:11:43
言語 Java8
(openjdk 1.8.0.222)
結果
AC  
実行時間 593 ms
コード長 1,157 Byte
コンパイル時間 2,587 ms
使用メモリ 57,936 KB
最終ジャッジ日時 2019-10-11 08:51:38

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 111 ms
21,236 KB
challenge02.txt AC 591 ms
56,756 KB
challenge03.txt AC 209 ms
27,316 KB
challenge04.txt AC 212 ms
27,320 KB
sample1.txt AC 115 ms
21,432 KB
sample2.txt AC 111 ms
21,240 KB
sample3.txt AC 114 ms
21,268 KB
sample4.txt AC 112 ms
21,244 KB
test1.txt AC 593 ms
57,936 KB
test2.txt AC 123 ms
21,388 KB
test3.txt AC 155 ms
26,520 KB
test4.txt AC 298 ms
31,444 KB
test5.txt AC 289 ms
31,448 KB
test6.txt AC 295 ms
31,452 KB
test7.txt AC 269 ms
29,808 KB
test8.txt AC 245 ms
28,844 KB
test9.txt AC 209 ms
27,376 KB
test10.txt AC 209 ms
27,332 KB
テストケース一括ダウンロード

ソースコード

diff #
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Scanner;


public class Y430 {
	Y430() throws Exception {
		Scanner in = new Scanner(System.in);
		PrintStream out = new PrintStream(System.out);
		
		String s = in.next();
		int m = in.nextInt();
		String[] w = new String[m];
		
		for (int i = 0; i < m; i++) {
			w[i] = in.next();
		}
		
		HashMap<Long, Integer>[] hashMap = new HashMap[11];
		
		for (int i = 0; i < 11; i++) {
			hashMap[i] = new HashMap();			
		}
		
		for (int i = 0; i < s.length(); i++) {
			for (int j = 1; j <= 10 && i + j <= s.length(); j++) {
				Long x = encode(s.substring(i,  i+j));
				Integer g = hashMap[j].get(x);
				
				if (g == null) g = 0;
				g += 1;
				hashMap[j].put(x, g);
			}
		}
		
		int answer = 0;
		for (int i = 0; i < m; i++) {
			Long x = encode(w[i]);
			Integer g = hashMap[w[i].length()].get(x);
			if (g != null) answer += g;
		}

		
		out.println(answer);
	}
	
	long encode(String s) {
		long x = 0;
		for (int i = 0; i < s.length(); i++) {
			x = x * 26 + (int)s.charAt(i) - 'A';
		}
		return x;
	}

	public static void main(String argv[]) throws Exception {
		new Y430();
	}
}
0