結果

問題 No.430 文字列検索
ユーザー hermione17
提出日時 2016-10-03 00:11:43
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 543 ms
コード長 1,157 Byte
コンパイル時間 2,362 ms
使用メモリ 69,308 KB
最終ジャッジ日時 2019-07-14 13:44:43

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 107 ms
32,268 KB
challenge02.txt AC 543 ms
67,588 KB
challenge03.txt AC 201 ms
39,220 KB
challenge04.txt AC 209 ms
37,312 KB
sample1.txt AC 107 ms
32,724 KB
sample2.txt AC 107 ms
30,164 KB
sample3.txt AC 107 ms
32,696 KB
sample4.txt AC 109 ms
31,896 KB
test1.txt AC 533 ms
69,308 KB
test2.txt AC 117 ms
32,732 KB
test3.txt AC 152 ms
37,616 KB
test4.txt AC 260 ms
41,132 KB
test5.txt AC 268 ms
41,532 KB
test6.txt AC 263 ms
40,700 KB
test7.txt AC 246 ms
39,304 KB
test8.txt AC 236 ms
39,824 KB
test9.txt AC 205 ms
38,884 KB
test10.txt AC 205 ms
38,388 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