접미사 오토마톤

모든 부분 문자열을 담는 최소 오토마톤.

다이아몬드 III

1강 모든 부분 문자열을 담는 최소 오토마톤 공식

정의와 목표

문자열 $$s$$ 의 접미사 오토마톤(SAM) 은 $$s$$ 의 모든 부분 문자열을 인식하는 최소 DFA다. 놀랍게도 상태 수가 $$O(n)$$ , 전이 수가 $$O(n)$$ 이며 $$O(n)$$ 에 온라인으로 구성된다. 서로 다른 부분 문자열 개수, 최장 공통 부분 문자열, $$k$$ 번째 부분 문자열 등 부분 문자열 문제를 일괄 처리한다.

endpos 동치류

부분 문자열 $$t$$ 의 등장 끝 위치 집합을 $\mathrm{endpos}(t)$ 라 하자. 두 부분 문자열이 같은 endpos 집합을 가지면 한 상태로 묶인다. 한 상태가 표현하는 부분 문자열들은 길이가 연속 구간 $[\,len(\text{link}) + 1,\ len\,]$ 을 이루며, 서로 접미사 관계다. 상태 수가 $$O(n)$$ 인 이유가 이 동치류의 개수 한계에 있다.

suffix link

상태 $$v$$ 의 suffix link $$link(v)$$ 는 " $$v$$ 가 표현하는 가장 짧은 부분 문자열의 한 글자 짧은 접미사" 가 속한 상태를 가리킨다. suffix link들은 $$O(n)$$ 개 노드의 트리(link tree)를 이루며, 이 트리는 사실상 $$s$$ 의 역순 문자열의 접미사 트리와 동형이다. 많은 응용이 이 link tree 위의 트리 DP로 풀린다.

온라인 구성

문자를 하나씩 끝에 붙이며 상태를 늘린다. 현재 끝 상태 last 에서 새 글자 $$c$$ 로의 전이를 따라 올라가며:

전이가 없으면 새 상태로 연결,
전이가 있으면 길이 조건에 따라 상태 복제(clone) 가 필요할 수 있다.

clone은 "이미 존재하는 상태가 새 글자 때문에 endpos가 갈라질 때" 길이만 줄인 사본을 만들어 link 구조를 보정한다. 각 글자 추가가 amortized $$O(1)$$ (알파벳 상수) 이라 전체 $$O(n)$$ .

핵심 사실 요약

항목	값
상태 수	$\le 2n-1$
전이 수	$\le 3n-4$
서로 다른 부분 문자열 수	$\sum_v (len(v) - len(link(v)))$
어떤 부분 문자열의 등장 횟수	link tree 서브트리의 endpos 크기

2강 SAM 구현과 응용 공식

표준 구성 코드

#include <bits/stdc++.h>
using namespace std;

struct SAM {
    struct State { int len, link; map<char,int> next; };
    vector<State> st;
    int last;
    SAM() { st.push_back({0, -1, {}}); last = 0; }  // 초기(빈) 상태

    void extend(char c) {
        int cur = st.size();
        st.push_back({st[last].len + 1, -1, {}});
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {    // 전이 없는 동안 연결
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;                    // 복제 불필요
            } else {
                int clone = st.size();               // 상태 복제
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
};

서로 다른 부분 문자열 개수

long long distinct_substrings(SAM& sam) {
    long long total = 0;
    for (int v = 1; v < (int)sam.st.size(); v++)
        total += sam.st[v].len - sam.st[sam.st[v].link].len;
    return total;   // 각 상태가 기여하는 길이 구간 크기의 합
}

자주 하는 실수

clone의 len. clone의 길이는 st[p].len + 1. st[q].len 을 쓰면 틀린다.
link/next 복사. clone은 $$q$$ 의 next 와 link 를 그대로 물려받고, $$q$$ 와 $$cur$$ 의 link를 clone으로 바꾼다.
전이 자료구조. map 은 간단하지만 느리다. 알파벳이 작고 작으면 고정 배열, 크면 unordered_map/정렬 벡터로 교체.
endpos 크기 계산. 원본 상태(clone 아님)는 등장 1, clone은 0으로 초기화한 뒤 link tree에서 자식→부모로 합산한다.

응용

문제	방법
서로 다른 부분 문자열 수	$\sum len - len(link)$
두 문자열의 최장 공통 부분 문자열	한쪽으로 SAM, 다른 쪽을 따라가며 길이 추적
부분 문자열 등장 횟수	link tree 서브트리 endpos 합
$$k$$ 번째 사전순 부분 문자열	전이 그래프 위 경로 수 누적 후 탐색

접미사 자동/배열과의 관계

SAM의 link tree는 역순 문자열의 접미사 트리와 동형이다. 따라서 접미사 배열·트리로 풀던 많은 문제를 SAM의 온라인· $$O(n)$$ 구성으로 더 단순하게 옮길 수 있다. 다중 문자열은 일반화 SAM(generalized SAM)으로 확장한다.