문제
풀이
Trie 자료 구조를 이용한 문제이다. root에서 add 함수를 이용하여 없는 단어는 추가하고, travel 함수로 root에 없으면 cnt+1이 되게끔 했다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys
from math import *
class trie:
def __init__(self):
self.root = {}
def add(self, list):
current = self.root
for i in list:
if i not in current:
current[i] = {}
def travel(self, string):
current = self.root
cnt = 0
for word in string:
if word in current:
cnt = cnt + 1
return cnt
N, M = map(int, input().split())
child = trie()
add_list = []
for _ in range(N):
s = input()
add_list.append(s)
child.add(add_list)
find_list = []
for _ in range(M):
s = input()
find_list.append(s)
print(child.travel(find_list))
