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에 게시됨