접미사 오토마톤 구성기
문자열의 모든 부분문자열을 인식하는 최소 DFA를 글자 하나씩 온라인으로 구성하는 과정을 보여주고, 서로 다른 부분문자열 개수를 셉니다.
"ana"은(는) "banana"의 부분문자열입니다
글자 추가 로그
| 'b' | 새 상태 1 | 복제 없음 |
| 'a' | 새 상태 2 | 복제 없음 |
| 'n' | 새 상태 3 | 복제 없음 |
| 'a' | 새 상태 4 | 상태 5 복제(clone) 발생 |
| 'n' | 새 상태 6 | 상태 7 복제(clone) 발생 |
| 'a' | 새 상태 8 | 상태 9 복제(clone) 발생 |
상태 표 (len, 접미사 링크, 전이)
| 상태 | len | link | 전이 |
| 0 | 0 | -1 | b→1 a→5 n→7 |
| 1 | 1 | 0 | a→2 |
| 2 | 2 | 5 | n→3 |
| 3 | 3 | 7 | a→4 |
| 4 | 4 | 9 | n→6 |
| 5 | 1 | 0 | n→7 |
| 6 | 5 | 7 | a→8 |
| 7 | 2 | 0 | a→9 |
| 8 | 6 | 9 | · |
| 9 | 3 | 5 | n→6 |
사용 방법
- 1문자열을 입력합니다.
- 2글자를 하나씩 추가하며 상태·전이가 만들어지는 과정을 확인합니다(clone 발생 여부 포함).
- 3서로 다른 부분문자열 개수와 부분문자열 판별 결과를 확인합니다.
자주 묻는 질문
각 상태는 문자열 안에서 "끝나는 위치들의 집합이 같은 부분문자열들의 묶음"을 나타냅니다. 루트에서 전이를 따라가 끝까지 도달할 수 있으면 그 경로의 글자열이 원문의 부분문자열이라는 뜻입니다 — 그래서 이 그래프 하나로 모든 부분문자열을 인식할 수 있습니다.
각 상태의 len(그 상태가 나타내는 가장 긴 부분문자열의 길이)에서 접미사 링크가 가리키는 상태의 len을 뺀 값을 모든 상태(루트 제외)에서 더합니다. 모든 부분문자열을 나열해 집합에 넣는 방식보다 훨씬 빠릅니다.
접미사 배열은 정렬된 접미사 "목록"이고, 접미사 오토마톤은 상태-전이로 이뤄진 "그래프"입니다. 접미사 오토마톤은 부분문자열 판별이나 개수 세기에서 상태 수만큼만 보면 되는 경우가 많아 목적에 따라 접미사 배열보다 간결하게 쓰일 수 있습니다.
새 글자를 추가하다가 이미 있는 전이를 만났는데 그 전이가 가리키는 상태의 len이 기대한 값과 다르면, 그 상태 하나가 서로 다른 두 역할(기존 부분문자열들의 몫과 새로 추가되는 접미사의 몫)을 동시에 맡고 있다는 뜻입니다. 이 상태를 복제해 역할을 분리해야 정확한 최소 DFA가 유지됩니다 — 알고리즘에서 가장 까다로운 부분입니다.
알아두면 좋은 점
- "ab"·"aa" 같은 짧은 문자열의 상태·전이·접미사 링크를 손으로 계산해 정확히 일치하는지 검증했습니다.
- clone이 실제로 필요한 문자열(abcbc, aabb 등)과 무작위 짧은 문자열 200개에서, 상태 기반으로 센 서로 다른 부분문자열 개수가 모든 부분문자열을 나열해 센 값과 정확히 일치하는지 검증했습니다.
- 부분문자열 판별 결과도 브루트포스 대조로 확인했습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.