Trie 트리 최적화를 통한 문자열 집합 처리 기법
문제 개요
문자열과 연관된 값들의 집합이 주어졌을 때, Trie 자료구조를 활용하여 유효한 구조인지 판별하고 최소 노드 개수를 구하는 문제입니다.
무효 조건 분석
다음 상황에서는 유효한 Trie 구조를 구성할 수 없습니다:
동일한 문자열이 서로 다른 값을 가지는 경우
여러 값들이 동일한 LCA 노드를 공유하는 경우
루트에서 LCA 노드까지의 경로에 제한된 노드가 존 ...
10월 9일 01:37에 게시됨
주요 알고리즘 및 자료구조 구현 템플릿 요약
KMP 문자열 매칭 (KMP Pattern Matching)
패턴 문자열 내의 접두사와 접미사가 일치하는 최대 길이를 계산하여 불필요한 비교를 줄이는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> compute_pi(const string& p) {
int m = p.size();
vector<int> pi(m, 0);
...
9월 19일 12:04에 게시됨
KMP 알고리즘과 문자열 검색 패턴 매칭 기법 종합 정리
문자열 접두사-접미사 매칭 문제 개요
여러 문자열의 접두사와 접미사를 매칭하는 문제는 일반적으로 전처리 과정을 통해 해결한다.
고정된 단어 개수를 가진 문자열 배열 s[n]이 주어졌을 때, 각 문자열을 cin으로 입력받아 처리한다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 여러 문자열 매칭을 위한 전처리 연산
}
}
...
7월 17일 02:04에 게시됨
AC 자동기와 Luogu 문제 해결: P3808 및 P3796
AC 자동기概述
AC 자동기(Aho-Corasick Automaton)는 여러 개의 패턴을 동시에 검색할 때 사용하는高效的인 알고리즘이다. KMP 알고리즘의 확장판이라고 볼 수 있으며, Trie 트리와 실패 함수(Failure Function)를 결합하여 구현한다. 이 알고리즘은 텍스트 하나에서 여러 개의 패턴이 등장하는 횟수를 모두 찾을 수 있다.
문제介绍
본 article에서는 Luogu의 두 가지 ...
6월 21일 00:20에 게시됨
Trie 자료구조 문제 풀이 분석
Luogu P6587 시퀀스 최적화
제약 조건 \(x \le 20\) 활용, ID의 하위 \(x\) 비트를 Trie 구조와 세그먼트 트리 기법으로 처리
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int MAX_NODES = 4e6 + 5, MAX_ELEMS = 2e5 + 5;
int elem_count, query_count, base_data[MAX_ELEMS];
int child_nodes[MAX_ELEMS*20][2] ...
6월 9일 21:15에 게시됨