KMP 문자열 매칭 알고리즘 C++ 구현과 next 배열 생성 원리
KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 매칭 문제를 해결하는 효율적인 알고리즘으로, 기존의 브루트 포스 방식이 O(n*m)의 시간 복잡도를 가지는 반면, 패턴 문자열을 전처리하여 next 배열을 생성함으로써 O(n+m)의 시간 복잡도로 최적화합니다(여기서 n은 메인 문자열의 길이, m은 패턴 문자열의 길이). 본 글에서는 핵심 원리를 바탕으로 C++ 코드를 통해 KMP 알 ...
6월 12일 22:20에 게시됨
적용된 알고리즘과 문제 해결 전략
총점: \(100+100+30+45=275\)
시작 10분 동안 문제 A에 접근했으나, 한 시간 후 포기하고 다른 문제로 이동.
문제 B를 빠르게 해결한 후 C에 도전하였으나 실패.
D의 폭력적인 해법을 작성하고 남은 30분 동안 다시 A를 시도.
A: H 군의 블록
상단과 하단의 숫자를 모두 세그먼트 트리에 추가합니다. 만약 숫자가 두 번 이상 등장하면 이를 후보로 설정하며, 각 단계에서 ...
6월 4일 03:09에 게시됨
AC 자동기 이해하기: 문자열 매칭의 상태 기계적 접근
자동기와 문자열 알고리즘의 연결 고리
문자열 처리 알고리즘에서 KMP, 트라이(Trie), AC 자동기(Aho-Corasick Automaton) 등은 각각 독특한 구조를 가지며, 이들의 핵심 개념은 모두 유한 상태 기계(Finite State Machine)에 근거한다. 이는 입력 문자열을 하나씩 소비하면서 내부 상태를 전이시키고, 특정 조건에서 패턴 일치를 감지하는 방식으로 동작한다.
상태 기계 ...
5월 30일 04:00에 게시됨