팰린드롬 오토마타(Palindrome Automaton, PAM)는 문자열 내 모든 회문 부분열을 효율적으로 관리하는 자료구조입니다. 이 구조는 O(n) 시간 복잡도로 회문 관련 문제를 해결할 수 있도록 설계되었으며, 두 개의 트리 계층 구조를 기반으로 동작합니다.

팰린드롬 오토마타는 홀수 길이 회문을 처리하는 기준 노드(인덱스 1)와 짝수 길이 회문을 처리하는 기준 노드(인덱스 0)로 구성됩니다. 각 노드는 특정 회문을 표현하며, 다음과 같은 핵심 속성을 가집니다:

• nodeLength: 해당 노드가 표현하는 회문의 길이 (기준 노드 0은 0, 기준 노드 1은 -1)
• failureLink: 현재 회문의 최장 진 접미사 회문을 가리키는 포인터
• transition: 문자별 전이 테이블 (트라이 구조와 유사)

기준 노드 1의 길이를 -1로 설정한 이유는 단일 문자 회문 처리를 단순화하기 위함입니다. 예를 들어, 문자 'a'를 처리할 때 i - nodeLength[1] - 1 = i가 되어 자연스럽게 매칭됩니다. 이 구조는 회문의 부분 회문 포함 관계를 활용하여 중복 계산을 방지합니다.

문자열 처리 알고리즘의 핵심은 findFailure 함수에 있습니다. 이 함수는 새로운 문자를 추가할 때 기존 최장 회문 접미사에서 시작해 유효한 확장을 찾는 역할을 수행합니다:

int findFailure(int currentNode, int position) {
    while (position - nodeLength[currentNode] <= 1 || 
           inputString[position - nodeLength[currentNode] - 1] != inputString[position]) {
        currentNode = failureLink[currentNode];
    }
    return currentNode;
}

새 노드 생성 시에는 다음과 같은 절차를 따릅니다:

1. 현재 위치에서 유효한 회문 접두사를 findFailure로 탐색
2. 해당 접두사에 새 문자를 추가할 수 있는지 확인
3. 전이 경로가 없을 경우 새 노드 생성 및 길이 설정 (nodeLength[newNode] = nodeLength[current] + 2)
4. 새 노드의 실패 링크를 기존 구조에서 파생된 값으로 초기화

다음은 회문 개수를 카운팅하는 구현 예시입니다. 각 위치에서 끝나는 회문의 총 개수는 현재 노드의 실패 링크 경로 상 모든 노드 수와 동일합니다:

class PalindromeProcessor {
private:
    vector<array<int, 26>> transition;
    vector<int> nodeLength, failureLink, palindromeCount;
    int nodeCount, currentLongest;

public:
    PalindromeProcessor() : 
        transition(2), nodeLength(2), 
        failureLink(2), palindromeCount(2) 
    {
        nodeCount = 1;
        nodeLength[0] = 0; 
        nodeLength[1] = -1;
        failureLink[0] = failureLink[1] = 1;
    }

    void addCharacter(char c, int pos) {
        int current = findFailure(currentLongest, pos);
        int charIndex = c - 'a';
        
        if (!transition[current][charIndex]) {
            nodeCount++;
            transition.push_back(array<int, 26>());
            nodeLength.push_back(nodeLength[current] + 2);
            failureLink.push_back(0);
            palindromeCount.push_back(0);
            
            int parentFail = findFailure(failureLink[current], pos);
            failureLink[nodeCount] = transition[parentFail][charIndex];
            palindromeCount[nodeCount] = palindromeCount[failureLink[nodeCount]] + 1;
            transition[current][charIndex] = nodeCount;
        }
        currentLongest = transition[current][charIndex];
    }
};

시간 복잡도 분석은 KMP 알고리즘과 유사합니다. 실패 링크 이동은 트리 깊이를 단조 감소시키며, 각 문자 처리 시 최대 2n 번의 이동만 발생합니다. 이는 전체적으로 O(n) 시간과 O(n|Σ|) 공간을 소요합니다. 본 구조는 회문 관련 문제에서 본질적 회문 부분열 개수 계산, 최장 이중 회문 탐색 등 다양한 응용이 가능합니다.