Trie

Trie 자료구조.

Autocomplete이나 Dictionary에 주로 사용된다.

 

시간복잡도는 HashMap에 입력할땐 O(1), 찾을땐 O(1) 이므로,

a, b, c만큼의 O(a) | O(b) | O(c) 가 발생한다.

import sys
input = sys.stdin.readline

class TrieNoode:
    def __init__(self):
        self.children={}
        self.endOfWord=False

class Trie:
    def __init__(self):
        self.root=TrieNoode()

    def insert(self, word):
        cur = self.root
        for char in word:
            if char not in cur.children:
                cur.children[char] = TrieNoode()
            cur = cur.children[char]

    def search(self, word):
        cur = self.root
        for char in word:
            if char not in cur.children:
                return False
            cur = cur.children[char]
        return cur.endOfWord

    def startsWith(self, prefix):
        cur = self.root
        for char in prefix:
            if char not in cur.children:
                return False
            cur = cur.children[char]
        return True

a, b, c = map(int, input().split())
trie = Trie()
for _ in range(a):
    trie.insert(input().rstrip())
cnt = 0
for _ in range(b):
    if trie.search(input().rstrip()):
        cnt += 1
print(cnt)

cnt = 0
for _ in range(c):
	if trie.startsWith(input().rstrip()):
        cnt += 1
print(cnt)