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