후위 자동기(정규화된 후위 자동기, SAM)는 문자열 처리에서 매우 강력한 도구로, 다양한 문자열 문제에 적용 가능하다. 아래는 대표적인 후위 자동기 기반 문제들을 정리한 내용이다.
기본 구조: 후위 자동기 생성
후위 자동기는 현재 상태를 기준으로 다음 문자를 처리하며, 각 노드는 특정 접미사의 공통 부분을 나타낸다. 주요 구성 요소는 다음과 같다:
len: 해당 상태가 표현하는 최대 길이.fa: 부모 상태 (접미사 링크).ch[26]: 다음 상태로 이동할 수 있는 문자 전이.
struct Node {
int len, fa;
int ch[26];
} a[N];
void extend(int c) {
int p = last, np = ++tot;
last = np;
a[np].len = a[p].len + 1;
while (p && !a[p].ch[c]) {
a[p].ch[c] = np;
p = a[p].fa;
}
if (!p) a[np].fa = 1;
else {
int q = a[p].ch[c];
if (a[q].len == a[p].len + 1)
a[np].fa = q;
else {
int nq = ++tot;
a[nq] = a[q];
a[nq].len = a[p].len + 1;
a[q].fa = a[np].fa = nq;
while (p && a[p].ch[c] == q) {
a[p].ch[c] = nq;
p = a[p].fa;
}
}
}
}
문제 1: 가장 긴 반복되는 부분문자열 (P3804)
입력된 문자열에서 여러 번 등장하는 부분문자열 중 가장 긴 것의 길이를 찾는 문제.
각 노드의 f 값은 해당 상태가 포함하는 모든 부분문자열의 등장 횟수를 의미한다. 트리 구조에서 후위 순회로 합산한 뒤, f[u] * len[u]를 최댓값으로 갱신.
ll ans = 0;
void dfs(int u) {
for (int i = h[u]; i; i = ne[i])
dfs(ver[i]), f[u] += f[ver[i]];
if (f[u] > 1)
ans = max(ans, f[u] * a[u].len);
}
문제 2: 문자열 검색 (P5231 – JSOI2012)
주어진 문자열의 접두사가 다른 문자열 내에서 얼마나 잘 일치하는지 확인. 후위 자동기 상에서 탐색을 진행하며, 매칭 가능한 경우 깊이를 증가시키고, 불일치 시 부모로 이동.
int p = 1, ret = 0;
for (char c : query_str) {
int idx = char_to_idx(c);
if (a[p].ch[idx]) p = a[p].ch[idx], ret++;
else break;
}
문제 3: 정확히 k번 등장하는 부분문자열의 최대 길이 (P5341 – TJOI2019)
k번 등장하는 부분문자열 중 가장 긴 것을 찾는다. 등장 횟수를 계산한 후, 차분 배열을 이용해 등장 횟수가 정확히 k번인 구간을 추적.
void dfs(int x) {
for (int i = h[x]; i; i = ne[i])
dfs(ver[i]), f[x] += f[ver[i]];
if (f[x] == k && a[x].len)
d[a[a[x].fa].len + 1]++, d[a[x].len + 1]--;
}
// 이후 차분 배열 누적합
for (int i = 0; s[i]; i++) {
d[i+1] += d[i];
if (d[i+1] >= mx) mx = d[i+1], ans = i+1;
}
문제 4: 두 개 이상의 문자열 공통 부분문자열 (LONGCS)
여러 문자열의 공통 부분문자열 중 가장 긴 것을 찾는다.
첫 번째 문자열로 SAM을 생성하고, 나머지 문자열들을 하나씩 탐색하며 현재까지 일치한 길이를 저장.
최종적으로 각 노드의 ans[i]는 모든 문자열에서 일치하는 최대 길이를 유지.
for (int j = 0; s[j]; j++) {
int c = s[j] - 'a';
while (p > 1 && !a[p].ch[c]) p = a[p].fa, t = a[p].len;
if (a[p].ch[c]) p = a[p].ch[c], t++;
now[p] = max(now[p], t);
}
dfs(1);
for (int i = 1; i <= tot; i++)
ans[i] = min(ans[i], now[i]);
문제 5: 길이별 최대 등장 횟수 (NSUBSTR)
길이가 x인 부분문자열의 최대 등장 횟수를 출력.
뒤에서부터 누적하여, 더 긴 길이의 결과가 더 짧은 길이에도 영향을 미친다는 성질을 활용.
void dfs(int x) {
for (int i = h[x]; i; i = ne[i])
dfs(ver[i]), f[x] += f[ver[i]];
ans[a[x].len] = max(ans[a[x].len], f[x]);
}
for (int i = n; i >= 1; i--)
ans[i] = max(ans[i], ans[i+1]);
문제 6: K번째 사전순 부분문자열 (P3975 – TJOI2015)
모든 부분문자열을 사전순으로 정렬했을 때, K번째에 위치한 문자열을 출력. 후위 자동기에서 각 노드 이후에 존재하는 부분문자열의 수를 미리 계산. 재귀적으로 선택하면서, 필요한 문자를 결정.
ll dfs2(int x) {
if (vis[x]) return f[x];
vis[x] = 1;
for (int i = 0; i < 26; i++) {
int y = a[x].ch[i];
if (y) f[x] += dfs2(y);
}
return f[x];
}
void query(int x, ll k) {
if (k <= siz[x]) return;
k -= siz[x];
for (int i = 0; i < 26; i++) {
int y = a[x].ch[i];
if (k > f[y]) k -= f[y];
else {
cout << ('a' + i);
query(y, k);
return;
}
}
}
문제 7: 가장 긴 회문 부분문자열 (P3649 – APIO2014)
맨처음에는 마나처 알고리즘으로 모든 회문 중심점을 찾고, 각 회문의 시작/끝 지점에 대해 후위 자동기에서 등장 횟수를 구해야 한다.
회문의 끝 지점에서 시작해, 부모로 올라가는 방식으로 endpos 집합을 확장.
이때, 배열 기반의 이중 분할(doubling)을 사용해 효율적으로 위로 이동.
void manacher() {
// ... 회문 중심점 탐색
for (int i = 1; i <= m; i++) {
if (i < mr) p[i] = min(p[2*mid-i], mr-i);
// ...
check(id[i-p[i]+2], id[i+p[i]-2]);
}
}
void build() {
for (int i = 1; i <= n; i++) extend(s[i]-'a', i);
// 후위 자동기 트리 정렬 및 등장 횟수 계산
for (int i = tot; i >= 1; i--) f[a[b[i]].fa] += f[b[i]];
// 배경 트리 구성
for (int i = 1; i <= tot; i++) {
int pos = b[i], fa = a[pos].fa;
d[pos] = d[fa] + 1;
st[pos][0] = fa;
for (int j = 1; (1<<j) <= d[pos]; j++)
st[pos][j] = st[st[pos][j-1]][j-1];
}
}
이처럼 후위 자동기는 단순한 문자열 매칭을 넘어, 공통 부분문자열, 등장 횟수, 사전순 조작, 회문 등의 고급 문제 해결에 필수적이다. 특히, 트리 구조와 동적 프로그래밍, 배경 이동 기법과 결합하면 복잡한 문제도 해결 가능하다.