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에 게시됨
후위 자동기 활용 문제 정리
후위 자동기(정규화된 후위 자동기, SAM)는 문자열 처리에서 매우 강력한 도구로, 다양한 문자열 문제에 적용 가능하다. 아래는 대표적인 후위 자동기 기반 문제들을 정리한 내용이다.
기본 구조: 후위 자동기 생성
후위 자동기는 현재 상태를 기준으로 다음 문자를 처리하며, 각 노드는 특정 접미사의 공통 부분을 나타낸다. 주요 구성 요소는 다음과 같다:
len: 해당 상 ...
6월 27일 21:19에 게시됨
K-주기 문자열 생성을 위한 최소 연산 횟수 계산
문제 설명
길이가 n인 문자열 word와 정수 k가 주어지며, k는 n의 약수입니다.
한 번의 연산에서, 임의의 두 인덱스 i와 j를 선택할 수 있습니다(여기서 0 <= i, j < n이고, 두 인덱스 모두 k로 나누어 떨어짐). 그런 다음 j에서 시작하는 길이가 k인 부분 문자열로 i에서 시작하는 길이가 k인 부분 문자열을 대체합니다. 즉, 부분 문자열 word[i…i + k - 1]을 부분 ...
6월 27일 03:45에 게시됨