트라이(trie) 파이썬, 백준 14425 파이썬

개요

문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다.

일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행합니다. 특징은 아래와 같습니다.

• N진 트리: 문자 종류의 개수에 따라 N이 결정됩니다. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성됩니다.
• 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지합니다.

구현 방법

1. 루트 노드는 공백을 유지한 채 첫 단어에 해당하는 노드를 생성합니다.
2. 아래 과정을 각 단어에 대해 반복하여 단어들을 모두 트리에 입력합니다.
   • 현재 위치한 글자에 대해 루트 자식노드 중 해당 글자가 공백 상태가 아니면 해당 글자로 이동합니다. 공백 상태라면 글자를 추가하고 그곳으로 이동합니다.

백준 14425 파이썬

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

class Node(object):
    def __init__(self, is_end):
        self.is_end = is_end
        self.child_node = {}

class Trie(object):
    def __init__(self):
        self.parent = Node(None)

    # 문자 삽입
    def insert(self, string):
        now_node = self.parent
        temp_length = 0
        for char in string:
            # 자식 노드들이 미생성된 문자열이면 새로 생성
            if char not in now_node.child_node:
                now_node.child_node[char] = Node(False)

            now_node = now_node.child_node[char]
            temp_length += 1
            if temp_length == len(string):
                now_node.is_end = True

    # 문자열이 존재하는지 탐색
    def search(self, string):
        now_node = self.parent
        temp_length = 0
        for char in string:
            if char not in now_node.child_node:
                break
            now_node = now_node.child_node[char]
            temp_length += 1
            if temp_length == len(string) and now_node.is_end:
                return True
        return False

my_trie = Trie()
for i in range(N):
    word = input().strip()
    my_trie.insert(word)
cnt = 0
for i in range(M):
    word = input().strip()
    if my_trie.search(word):
        cnt += 1
print(cnt)