[ 트라이 ] 알고리즘

 

 

1.  개념

 

 

트라이 알고리즘 : 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조

 

특징

-  N진 트리 : 문자 종류의 개수에 따라 N이 결정

-  루트 노드는 항상 공백 상태

 

 

 

2.  구현

 

 

(1) 초기 설정

- 루트 노드는 공백으로 설정

(2) 단어 삽입

- 루트 노드부터 검색

- 단어를 이루는 각 알파벳에 대해

   =>  해당 알파벳이 공백 : 해당 알파벳 노드 생성

          해당 알파벳이 공백X : 해당 알파벳 노드로 이동

 

 

 

 

3.  문제

 

# 1  문자열 집합 - 백준 14425번

https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

 

from sys import stdin
input = stdin.readline

# 노드 클래스 생성
class Node(object):
    def __init__(self, isEnd):
        self.isEnd = isEnd  # 마지막 문자열 여부
        self.childNode = {}  # 자식 노드


# 트라이 클래스 생성
class Trie(object):
    def __init__(self):
        self.parent = Node(None)  # parent : 부모 노드 저장 변수  ->  루트 노드는 공백

 	# 문자 삽입 함수
    def insert(self, string):
        nowNode = self.parent
        temp_length = 0
        for char in string:
        	# 자식 노드에 없는 문자면 노드 새로 생성
            if char not in nowNode.childNode:
                nowNode.childNode[char] = Node(char)
			# 자식 노드 문자로 이동
            nowNode = nowNode.childNode[char]
            temp_length += 1
            # 마지막 문자면 마지막 문자 표시
            if temp_length == len(string):
                nowNode.isEnd = True

	# 문자 찾기 함수
    def search(self, string):
        nowNode = self.parent
        temp_length = 0
        for char in string:
        	# 문자 존재하면 True 리턴
            if char in nowNode.childNode:
                nowNode = nowNode.childNode[char]
                temp_length += 1
                if temp_length == len(string) and nowNode.isEnd == True:
                    return True
            # 문자 존재하지 않으면 False 리턴
            else:
                return False
        # 문자 존재하지 않으면 False 리턴
        return False


n, m = map(int, input().split())
myTrie = Trie()  # 트라이 객체 생성

for _ in range(n):
    word = input().strip()
    myTrie.insert(word)

result = 0

for _ in range(m):
    word = input().strip()
    if myTrie.search(word):
        result += 1

print(result)

 

으어.. 어렵다..