[Python]문자열 알고리즘1 백준 14425

 문제

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

트라이 구조를 통해 구현해보고 수정해보았다.

먼저 트라이 구조를 직접 구현하였을때는 pypy3로 겨우 통과했다.

원래는 배열을 사용하여야 하나 그냥 딕셔너리를 통해 트라이 구조만을 구현했다.

#트라이 구조에 필요한 노드
class Node:
    def __init__(self,chr):
        self.chr=chr
        self.child={}
        self.check=False
 
 
#해당 문자열 잇는지 확인
def triedfs(node,s,n):
    if len(s)==n:#문자열의 끝까지같으면
        if node.check:#문자열 끝표시가 있으면
            result.append(s)
            return
        else:
            return
    if s[n] in node.child:#재귀를 통해 확인
        triedfs(node.child[s[n]], s, n + 1)
    return
 
 
#trie 구조
trie=Node('')
N,M=map(int,input().split())
for _ in range(N):
    tmp = trie
    s=input().rstrip()
    for i in s:#문자열 추가
        check=True
        if i in tmp.child:#해당 문자가 잇다면
            tmp=tmp.child[i]#해당 문자의 노드로 이동
            if i==s[-1]:#문자끝 표시
                tmp.check=True
        else:
            a=Node(i)#노드생성후 추가
            tmp.child[i]=a
            tmp=a
            if i == s[-1]:#문자끝표시
               tmp.check=True
 
count=0
result=[]
for _ in range(M):
    p=input().rstrip()
    triedfs(trie,p,0)
 
print(len(result))
 

그냥 딕셔너리를 활용하면 더욱 간결하고 빠르게 구현할수있다.

파이썬 딕셔너리는 해시 값을 사용하기 때문에 O(1)의 시간이 걸린다.

import sys
n,m = map(int,input().split())
cnt = 0
strings = {sys.stdin.readline() for i in range(n)}
for j in range(m):
    tmp = sys.stdin.readline()
    if tmp in strings:
        cnt += 1
print(cnt)