問題: BOJ 14425 — 文字列集合 · English · 한국어
N個の文字列を保存し、M個の文字列を確認します。確認する文字列のうち、保存した文字列に含まれるものがいくつあるか数えます。すべての文字列は英小文字のみで構成されます。
ハッシュセット
入力文字列をHashSet<String>に保存します。同じ文字列を複数回挿入してもセットの内容は変わらないため、保存文字列の重複は結果に影響しません。各クエリではcontainsを使って文字列全体が完全一致するかを調べ、存在すれば個数を増やします。各クエリは1回だけ処理するため、答えへの寄与は最大1です。
長さLの文字列をハッシュセットに挿入または検索する時間は、ハッシュ計算と文字列内容の比較を含めて期待O(L)です。挿入する文字列とクエリ文字列全体に対する期待時間計算量はO(全体の文字数)です。空間計算量は、異なる保存文字列の全体の文字数に対してO(全体の文字数)です。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int[] arr = getArr();
int n = arr[0], m = arr[1];
Set<String> words = new HashSet<>();
for(int i = 0; i < n; i++) words.add(br.readLine());
int count = 0;
for(int i = 0; i < m; i++) {
if(words.contains(br.readLine())) count++;
}
System.out.print(count);
}
static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
}