[코드 스니펫]트라이(Trie) 자료구조

기본 구현

class Trie {

	public static class Node {
		private boolean isEnd;
		private final Node[] next;

		public Node(int size) {
			this.isEnd = false;
			this.next = new Node[size];
		}

		public Node next(int v) {
			return this.next[v];
		}

		public boolean isEnd() {
			return isEnd;
		}
	}

	private final char start;
	private final int size;
	private final Node root;

	public Trie(char start, char end) {
		this.start = start;
		this.size = end - start + 1;
		this.root = new Node(size);
	}

	public void make(String s) {
		Node now = root;

		for (char c : s.toCharArray()) {
			if (now.next[c - start] == null) {
				now.next[c - start] = new Node(size);
			}
			now = now.next[c - start];
		}

		now.isEnd = true;
	}

	public Node getRoot() {
		return root;
	}
}

 

사용 예

백준 14425번 문제

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Trie {

	public static class Node {
		private boolean isEnd;
		private final Node[] next;

		public Node(int size) {
			this.isEnd = false;
			this.next = new Node[size];
		}

		public Node next(int v) {
			return this.next[v];
		}

		public boolean isEnd() {
			return isEnd;
		}
	}

	private final char start;
	private final int size;
	private final Node root;

	public Trie(char start, char end) {
		this.start = start;
		this.size = end - start + 1;
		this.root = new Node(size);
	}

	public void make(String s) {
		Node now = root;

		for (char c : s.toCharArray()) {
			if (now.next[c - start] == null) {
				now.next[c - start] = new Node(size);
			}
			now = now.next[c - start];
		}

		now.isEnd = true;
	}

	public Node getRoot() {
		return root;
	}
}

public class App {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		Trie t = new Trie('a', 'z');

		for (int i = 1; i <= N; i++) {
			t.make(br.readLine());
		}

		List<String> checks = new ArrayList<>(M);
		for (int i = 1; i <= M; i++) {
			checks.add(br.readLine());
		}

		Trie.Node root = t.getRoot();

		int result = 0;

		for (String check : checks) {
			Trie.Node now = t.getRoot();

			boolean ok = true;
			for (char c : check.toCharArray()) {
				if (now.next(c - 'a') == null) {
					ok = false;
					break;
				}

				now = now.next(c - 'a');
			}

			ok &= now.isEnd();
			result += (ok ? 1 : 0);
		}

		bw.write(String.valueOf(result));
		br.close();
		bw.close();
	}
}