키 트리: 구조 및 구현 방식

키 트리는 문자열이나 키 값을 효율적으로 저장하고 검색하기 위해 사용되는 특수한 형태의 트리 자료구조입니다. 주로 자동 완성 기능, 사전 애플리케이션, IP 라우팅 테이블 등 문자열 기반의 빠른 검색 성능이 중요한 분야에서 활용됩니다. 키 트리는 키를 구성하는 각 문자를 노드에 저장하며, 이 노드들이 연결되어 전체 키를 나타내는 경로를 형성합니다. 이러한 구 ...

10월 1일 14:36에 게시됨

KMP 알고리즘과 기타 문자열 처리 기법 활용

KMP 알고리즘의 nxt 배열을 살펴보겠습니다. 답은 n - nxt[n]으로 구할 수 있습니다. 코드 #include <iostream> #include <vector> #include <string> void compute_next_array(int n, const std::string& s, std::vector<int>& nxt) { int j = 0; for (int i = 1; i < n; ++i) { while (j > 0 && s[i] != ...

7월 21일 19:08에 게시됨

AC 자동기 이해하기: 문자열 매칭의 상태 기계적 접근

자동기와 문자열 알고리즘의 연결 고리 문자열 처리 알고리즘에서 KMP, 트라이(Trie), AC 자동기(Aho-Corasick Automaton) 등은 각각 독특한 구조를 가지며, 이들의 핵심 개념은 모두 유한 상태 기계(Finite State Machine)에 근거한다. 이는 입력 문자열을 하나씩 소비하면서 내부 상태를 전이시키고, 특정 조건에서 패턴 일치를 감지하는 방식으로 동작한다. 상태 기계 ...

5월 30일 04:00에 게시됨