회문 트리

회문 트리(영어: palindromic tree, EERTREE)는 모든 부분 회문에 대한 정보를 $n$개 회문의 크기보다 더 강력한 다른 형식으로 저장하는 자료 구조입니다. 이 자료 구조는 2014년 여름 페트로자보츠크 캠프에서 미하일 루빈치크가 제안했습니다.

보조정리. 문자열에는 서로 다른 부분 회문이 최대 $n$개 존재합니다.

증명. 문자열에 문자를 하나씩 덧붙여 나간다고 하고, 현재 $r$개의 문자를 쓴 시점에 가장 긴 접미사 팰린드롬이 $s_{l:r}$이라고 합시다. 그리고 이 팰린드롬이 다시 접미사 팰린드롬 $s_{l’:r} = t$를 가진다고 합시다. 그러면 이 팰린드롬은 문자열 안에 $s_{l:l+r-l’} = t$로서 더 앞선 위치에도 등장합니다. 따라서 새 문자가 하나 추가될 때마다 문자열에 새로 생기는 팰린드롬은 많아야 하나이며, 그런 팰린드롬이 있다면 그것은 항상 가장 긴 접미사 팰린드롬입니다.

이 사실을 이용하면 문자열의 모든 회문에 다음과 같은 구조를 대응시킬 수 있습니다. 각 회문에서 오른쪽 절반을 취하고(예를 들어 $abacaba$에 대해서는 $caba$, $abba$에 대해서는 $ba$를 취합니다. 당분간은 짝수 길이 회문만 고려하겠습니다), 이 절반들을 모두 접두사 트리에 추가합니다. 이렇게 얻은 구조를 회문 트리라고 부르겠습니다.

순진한 구축 알고리즘은 최악의 경우 $O(n^2)$에 동작하지만, 이를 더 효율적으로 수행할 수도 있습니다.

#선형 시간 구성

가장 긴 접미사 회문을 유지하겠습니다. 다음 문자 $c$를 덧붙일 때, 이 회문의 접미사 중 문자 $c$로 확장할 수 있는 가장 긴 것을 찾아야 합니다. 바로 그것이 새로운 가장 긴 접미사 회문이 됩니다.

이를 위해 아호-코라식 알고리즘과 비슷하게 진행합니다. 각 팰린드롬마다 $v$에서 그 가장 긴 접미사 팰린드롬으로 이어지는 접미사 링크 $l(v)$를 유지합니다. 다음 문자를 추가할 때는 필요한 전이를 수행할 수 있는 정점을 찾을 때까지 접미사 링크를 따라 올라갑니다.

적절한 정점에 이 전이가 존재하지 않았다면 새 정점을 만들어야 하며, 이 정점에도 자신의 접미사 링크가 필요합니다. 이를 찾기 위해 이전 접미사-회문의 접미사 링크를 따라 계속 올라가면서, 문자 $c$로 확장할 수 있는 두 번째 위치를 찾을 때까지 진행합시다.

const int maxn = 1e5, k = 26;

int s[maxn], len[maxn], link[maxn], to[maxn][k];

int n, last, sz;

void init() {
    s[n++] = -1;
    link[0] = 1;
    len[1] = -1;
    sz = 2;
}

int get_link(int v) {
    while (s[n-len[v]-2] != s[n-1])
        v = link[v];
    return v;
}

void add_char(int c) {
    s[n++] = c;
    last = get_link(last);
    if (!to[last][c]) {
        len[sz] = len[last] + 2;
        link[sz] = to[get_link(link[last])][c];
        to[last][c] = sz++;
    }
    last = to[last][c];
}

여기서는 전이를 저장하기 위해 일반 배열을 사용했습니다. 여느 접두사 트리와 마찬가지로, 배열 대신 이진 탐색 트리, 해시 테이블, 단일 연결 리스트 등 점근적 복잡도를 약간 바꾸는 대가로 시간과 메모리를 맞바꿀 수 있게 해 주는 다른 구조를 사용할 수 있습니다.

#점근적 복잡도

알고리즘이 선형 시간에 동작함을 보이겠습니다. 문자열의 가장 긴 접미사 회문의 길이를 생각해 봅시다. 새 문자 하나가 추가될 때마다 이 길이는 최대 2만큼 증가합니다. 한편 접미사 링크를 따라 한 번 이동할 때마다 이 길이는 감소하므로, 첫 번째 접미사 회문을 찾는 과정은 분할 상환 선형 시간에 동작합니다.

두 번째 접미사 회문의 길이에 대해서도 같은 방식으로 추론하면(그 길이 역시 한 번에 최대 2만큼만 증가합니다), 새 정점을 생성할 때 접미사 링크를 다시 계산하는 작업 역시 전체적으로 선형 시간에 동작함을 알 수 있습니다.