회문 처리 최적화를 위한 팰린드롬 오토마타 핵심 구조 분석
팰린드롬 오토마타(Palindrome Automaton, PAM)는 문자열 내 모든 회문 부분열을 효율적으로 관리하는 자료구조입니다. 이 구조는 O(n) 시간 복잡도로 회문 관련 문제를 해결할 수 있도록 설계되었으며, 두 개의 트리 계층 구조를 기반으로 동작합니다.
팰린드롬 오토마타는 홀수 길이 회문을 처리하는 기준 노드(인덱스 1)와 짝수 길이 회문을 처리하는 기준 노드(인덱스 ...
9월 14일 09:56에 게시됨
문자열 동적 계획법: 부분 수열 카운팅, 삭제 연산, 그리고 편집 거리 최적화
1. 서로 다른 부분 수열의 개수 구하기
두 개의 문자열 text와 pattern이 주어졌을 때, text의 부분 수열 중 pattern과 일치하는 경우의 수를 계산하는 문제입니다. 부분 수열이란 원본 문자열에서 문자의 상대적 순서를 유지한 채 일부 문자를 제거하여 만들 수 있는 새로운 문자열을 의미합니다. 결과값은 32비트 부호 있는 정수 범위를 보장합니다.
class Solution {
pu ...
6월 16일 02:33에 게시됨