아호-코라식 알고리즘

우리가 언론을 통제하는 어느 권위주의 국가에서 기자로 일하고 있으며, 그 국가에서는 특정 정치적 사건을 언급하거나 특정 단어를 사용하는 것을 금지하는 법률이 때때로 공포된다고 가정해 봅시다. 이러한 검열을 프로그램으로 어떻게 효율적으로 구현할 수 있겠습니까?

더 형식적으로 말하면, 사전이라고 부르는 크기 $k$인 알파벳 위의 문자열 집합 $s_1, s_2, \ldots, s_m$(총길이 $n$)과 긴 텍스트 $t$가 주어진다고 합시다. 텍스트에 사전의 단어가 적어도 하나 있는지, 그리고 있다면 어느 위치에 있는지를 구해야 합니다.

우리는 이미 이 문제를 풀 수 있습니다. 예를 들어 각 단어의 등장 여부를 독립적으로 검사하여 $O(n \cdot |t|)$에, 또는 모든 짧은 부분 문자열을 해싱하여 $O(\max |s_i| \cdot |t|)$에 풀 수 있습니다. 그러나 우리는 여전히 $O(|t|)$의 확장 가능한 풀이를 원하며, 오늘은 우리의 문제를 해결할 오토마톤을 만들어 보겠습니다.

아호-코라식 알고리즘(창시자인 앨프리드 아호와 마거릿 코라식의 성을 따서 명명되었으며, 흔히 «붕어»라고도 불립니다)은 $O(nk)$의 시간과 메모리로 이 문자열 집합에 대한 접두사 트리를 구축한 다음, 이 트리를 바탕으로 이 문제뿐 아니라 다른 많은 문자열 문제에도 사용할 수 있는 오토마톤을 구축합니다. 이 알고리즘은 1975년에 발견되었으며, 그 이후로 텍스트 스트림 처리를 위한 시스템 프로그램에서 널리 사용되고 있습니다. 예를 들어 grep 유틸리티가 그렇습니다.

이 글의 저자는 업무상 아호-코라식 알고리즘을 무려 두 번이나 구현해야 했는데, 이는 다른 모든 「올림피아드용」 알고리즘보다 두 번 더 많은 횟수입니다.

#기본 아이디어

사전으로 트라이(접두사 트리)를 만듭시다. 사전의 문자열들이 서로의 부분 문자열이 아니라고 가정합시다. 이 경우 더 긴 문자열은 버릴 수 있지만, 나중에 보겠지만 이 조건은 사실 필요하지 않습니다.

문제를 해결하기 위해 문자를 하나씩 읽을 때마다 가장 긴 문자열에 해당하는 상태를 유지하는 오토마톤을 만들겠습니다. 이 문자열은 다음 조건을 동시에 만족합니다.

사전에 있는 어떤 문자열의 접두사이면서
지금까지 읽은 텍스트의 접미사입니다.

상태에 대해서는 이 정보만으로 충분합니다. 이 상태가 종료 상태로 표시되어 있으면 접미사가 사전의 어떤 문자열과 일치하므로 그 문자열을 출력합니다. 그렇지 않다면 정의에 따라 우리는 트라이가 받아들이는 가장 긴 접미사를 찾은 것인데, 그 접미사의 어떤 부분 문자열도 금지된 문자열이 아니므로 이 위치에는 금지된 단어가 하나도 포함되어 있지 않습니다.

어려운 부분은 이러한 오토마톤을 구성하는 것, 즉 접두사 트리의 상태와 새 문자가 주어졌을 때 지금까지 써 내려간 텍스트의 새 접두사의 접미사 중 트라이에 포함되는 가장 긴 접미사에 해당하는 정점을 빠르게 찾는 것입니다. 이를 위해 몇 가지 보조 개념이 필요합니다.

#접미사 링크

반(反)형식주의. 매번 “정점 $v$에 대응하는 문자열 $s$“처럼 번거롭게 쓰지 않도록, 앞으로는 정점과 트라이에서 그 정점에 대응하는 문자열을 동일시하기로 합시다.

정의. 접미사 링크 $l(v)$는 트라이가 받아들이는 $v$의 가장 긴 접미사에 대응하는 정점 $u \neq v$로 이어집니다.

정의. 오토마톤 전이 $\delta(v, c)$는 문자열 $v + c$의 접미사 중 트라이가 받아들이는 가장 긴 접미사에 해당하는 정점으로 이어집니다.

관찰. 전이가 이미 트라이에 존재한다면(이러한 전이를 직접 전이라고 부르겠습니다), 오토마톤 전이도 같은 곳으로 이어집니다.

오토마톤 전이는 바로 이 문제에서 우리에게 필요한 것입니다. 오토마톤 전이는 정확히 가장 긴 수락 가능한 접미사에 해당하는 정점으로 이어집니다.

#계산하는 방법

접미사 링크와 오토마톤 전이 사이에 다음과 같은 관계가 있음에 주목하십시오:

$l(s_{:n}) = \delta(l(s_{:n-1}), s_n)$: 부모로 이동하여 그 접미사 링크를 따라간 다음, 마지막 문자에 대한 오토마톤 전이를 따라가면 자기 자신의 접미사 링크를 얻게 됩니다.
직접 전이 $v \to_c u$가 존재하지 않으면 $\delta(v, c) = \delta(l(v), c)$입니다. 접미사 링크를 따라간 다음 문자 $c$에 대한 오토마톤 전이를 따라가면, 이 문자에 대한 자신의 오토마톤 전이를 얻습니다.

루트와 그 직접적인 자식들에 관해서는 몇 가지 미묘한 점이 있지만, 중요한 것은 우리가 방금 길이 $n$인 문자열에 대한 $l$과 $\delta$를 크기가 $(n-1)$ 이하인 문자열에 대한 $l$과 $\delta$로 표현했다는 점입니다. 따라서 접미사 링크와 오토마톤 전이는 방금 적어 둔 공식을 이용하여 동적 계획법으로 구할 수 있습니다.

#구현

접두사 트리와 비교하면, 직접 전이 배열 to와 정점의 “종결 여부” 외에 몇 가지 추가 정보를 저장해야 합니다:

to와 같은 크기의 오토마톤 전이 배열 go;
접미사 링크 link;
접미사 링크를 구하는 공식에 필요한 ‘부모’ 문자 pch.

라틴 알파벳으로 작업한다고 가정하면 다음과 같습니다:

const int k = 26;

struct Vertex {
    Vertex *to[k] = {0}, *go[k] = {0};
    Vertex *link = 0, *p;
    int pch;
    Vertex (int _pch, Vertex *_p) { pch = _pch, p = _p; }
};

Vertex *root = new Vertex(-1, 0);

문자열 추가도 거의 같습니다:

void add_string(string &s) {
    Vertex *v = root;
    for (char _c : s) {
        int c -= int(_c - 'a');
        if (!v->to[c])
            v->to[c] = new Vertex(c, v);
        v = v->to[c];
    }
}

DP go와 link는 «게으른 DP»로 계산하겠습니다. 이를 위해 자신의 결과를 기억하는 두 함수를 도입합니다:

// нам нужно объявить две функции, ссылающиеся друг на друга
// в C/C++ для этого нужно сигнатуру хотя бы одной из них объявить перед другой
Vertex* go(Vertex *v, int c);

Vertex* link(Vertex *v) {
    if (!v->link) {
        // для строк длины меньше двух суффиксная ссылка это корень
        if (v == root || v->p == root)
            v->link = root;
        else // в остальных случаях формула работает
            v->link = go(link(v->p), v->pch);
    }
    return v->link;
}

Vertex* go(Vertex *v, int c) {
    if (!v->go[c]) {
        // если переход есть, то автоматный должен вести туда же
        if (v->to[c])
            v->go[c] = v->to[c];
        // если перехода нет, но вершина корень, то нужно сделать петлю
        else if (v == root)
            v->go[c] = root;
        else // в остальных случаях формула работает
            v->go[c] = go(link(v), c);
    }
    return v->go[c];
}

bfs를 통해 오토마톤을 구축하는 것이 더 효율적이고 «깔끔합니다». 더 긴 문자열의 상태는 더 짧은 문자열에만 의존하므로 루트에서부터 «파동»을 퍼뜨릴 수 있기 때문입니다. 하지만 이 방법은 이해하고 구현하기가 더 어렵습니다.