Suffix Automaton과 KMP 비교 이해

suffix automaton과 KMP 알고리즘은 문자열 검색 및 문자열 구조 분석에 사용되는 도구이지만, 목적, 구조, 적용 범위에서 차이가 있습니다. 아래에 그 차이점을 자세히 설명드리겠습니다.

---

📌 1. 개념 및 목적

항목 Suffix Automaton (접미사 자동자) KMP 알고리즘

목적	문자열의 모든 부분 문자열을 빠르게 처리하거나 분석 (예: 부분 문자열 존재 여부, 갯수, 중복 등)	패턴 검색: 텍스트에서 주어진 패턴이 등장하는 위치를 빠르게 찾음
구조	DFA(Deterministic Finite Automaton)를 최소화한 형태의 유한 상태 기계	실패 함수(failure function)를 사용하는 상태 기반 검색 알고리즘
입력	하나의 문자열(기반 문자열 S)	패턴 문자열 P와 텍스트 문자열 T

---

🔍 2. 시간 복잡도

• Suffix Automaton
  • 구축 시간: O(N) (N = 문자열 길이)
  • 질의 응답 시간: O(M) (M = 질의 문자열 길이)
• KMP
  • 전처리 (실패 함수 생성): O(M)
  • 검색: O(N) (N = 텍스트 길이)

---

🔨 3. 사용 예시

✅ Suffix Automaton

• 특정 문자열 S의 모든 부분 문자열을 빠르게 분석할 때
• 예:
  • S에 X라는 문자열이 있는가?
  • S에 있는 서로 다른 부분 문자열의 수는?
  • S에 등장하는 가장 긴 중복된 부분 문자열은?
  • S의 접미사와 접두사가 같은 것들의 집합 분석

✅ KMP 알고리즘

• 긴 텍스트 T에서 패턴 P가 등장하는 위치만 빠르게 찾을 때
• 예:
  • "ababcab"이라는 패턴이 긴 텍스트에서 몇 번 등장하는가?
  • 문자열 비교 횟수를 줄여서 패턴 일치를 빠르게 찾음

---

🧠 구조 비교

🧱 Suffix Automaton

• 상태(State)들은 문자열의 접미사들을 표현
• 자동자에서 이동(Transition)은 다음 문자에 따라 이루어짐
• DAG (유향 비순환 그래프) 구조로 만들어져 중복 제거

🧩 KMP

• π 배열(실패 함수): 부분 일치 테이블
• 현재 위치에서 매칭 실패 시 어디서부터 다시 비교할지 결정

---

🔁 요약 정리

구분 Suffix Automaton KMP

목적	부분 문자열 분석	패턴 검색
데이터 구조	유한 상태 기계 (DFA)	실패 함수 기반
복잡도	O(N) 구축, O(M) 질의	O(N + M) 전체 검색
용도	부분 문자열 수, 중복, 존재 여부 등	패턴 매칭
확장성	Suffix Tree / Array 대체 가능	Boyer-Moore 등과 비교

---

❓ 예제 상황

• 텍스트 "abracadabra"에서 "cada"라는 패턴을 찾고 싶다 → KMP
• 텍스트 "abracadabra"에 존재하는 모든 서로 다른 부분 문자열의 수를 알고 싶다 → Suffix Automaton

---

좋습니다! 아래에 Python 코드 예제를 통해 Suffix Automaton과 KMP 알고리즘의 차이를 직접 확인하실 수 있도록 준비했습니다.

---

✅ 1. KMP 알고리즘 예제 (패턴 검색)

🔍 목적: 텍스트에서 특정 패턴의 모든 등장 위치를 찾기

def kmp_failure_function(pattern):
    n = len(pattern)
    failure = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and pattern[i] != pattern[j]:
            j = failure[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            failure[i] = j
    return failure

def kmp_search(text, pattern):
    failure = kmp_failure_function(pattern)
    result = []
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = failure[j - 1]
        if text[i] == pattern[j]:
            j += 1
            if j == len(pattern):
                result.append(i - j + 1)  # match found
                j = failure[j - 1]
    return result

# 사용 예시
text = "abracadabra"
pattern = "abra"
positions = kmp_search(text, pattern)
print(f"KMP: '{pattern}'는 다음 위치에서 발견됨:", positions)

출력 예시:

KMP: 'abra'는 다음 위치에서 발견됨: [0, 7]

---

✅ 2. Suffix Automaton 예제 (부분 문자열 존재 여부 확인)

🔍 목적: 주어진 텍스트에서 특정 문자열이 부분 문자열로 존재하는지 확인

def build_suffix_automaton(s):
    len_list = [0]
    link = [-1]
    nexts = [{}]
    last = 0

    for c in s:
        p = last
        curr = len(len_list)
        len_list.append(len_list[p] + 1)
        link.append(0)
        nexts.append({})
        while p != -1 and c not in nexts[p]:
            nexts[p][c] = curr
            p = link[p]
        if p == -1:
            link[curr] = 0
        else:
            q = nexts[p][c]
            if len_list[p] + 1 == len_list[q]:
                link[curr] = q
            else:
                clone = len(len_list)
                len_list.append(len_list[p] + 1)
                link.append(link[q])
                nexts.append(nexts[q].copy())
                while p != -1 and nexts[p][c] == q:
                    nexts[p][c] = clone
                    p = link[p]
                link[q] = link[curr] = clone
        last = curr
    return nexts

def contains_substring(nexts, substring):
    state = 0
    for c in substring:
        if c not in nexts[state]:
            return False
        state = nexts[state][c]
    return True

# 예제
nexts = build_suffix_automaton("abracadabra")
print(contains_substring(nexts, "cada"))  # True
print(contains_substring(nexts, "xyz"))   # False

 

🧠 요약

• KMP는 패턴이 어디에서 등장하는지 알려줍니다.
• Suffix Automaton은 패턴이 존재하는지만 빠르게 확인하고, 다양한 확장 질의(부분 문자열 수 등)도 가능합니다.

---

 

---

ADVANCED

Suffix Automaton을 이용한 고급 질의 2가지와 Python 코드

✅ 1. 중복 부분 문자열 개수 세기

📌 설명

• 중복 포함: "ababa"의 경우 "a"는 3번 등장 → 모두 세야 함
• 모든 상태(state)가 몇 개의 substring을 대표하는지 계산하고, 그것들의 등장 횟수를 더하면 됩니다.

---

🧩 구현

def count_substrings_with_duplicates(s):
    len_list = [0]
    link = [-1]
    nexts = [{}]
    size = [0]
    last = 0

    for c in s:
        p = last
        curr = len(len_list)
        len_list.append(len_list[p] + 1)
        link.append(0)
        nexts.append({})
        size.append(1)
        while p != -1 and c not in nexts[p]:
            nexts[p][c] = curr
            p = link[p]
        if p == -1:
            link[curr] = 0
        else:
            q = nexts[p][c]
            if len_list[p] + 1 == len_list[q]:
                link[curr] = q
            else:
                clone = len(len_list)
                len_list.append(len_list[p] + 1)
                link.append(link[q])
                nexts.append(nexts[q].copy())
                size.append(0)
                while p != -1 and nexts[p][c] == q:
                    nexts[p][c] = clone
                    p = link[p]
                link[q] = link[curr] = clone
        last = curr

    # 크기 전파
    order = sorted(range(len(len_list)), key=lambda x: -len_list[x])
    for u in order:
        if link[u] != -1:
            size[link[u]] += size[u]

    total = 0
    for i in range(1, len(len_list)):
        total += (len_list[i] - len_list[link[i]]) * size[i]
    return total

# 예제
print(count_substrings_with_duplicates("ababa"))  # 출력: 9

 

---

✅ 2. 가장 긴 공통 부분 문자열 (LCS: Longest Common Substring)

📌 설명

• 두 문자열 S1, S2에 대해 가장 긴 연속된 공통 부분 문자열을 구함
• S1로 Suffix Automaton을 만들고, S2를 따라가며 가장 긴 경로를 추적

---

🧩 구현

def build_suffix_automaton_basic(s):
    len_list = [0]
    link = [-1]
    nexts = [{}]
    last = 0
    for c in s:
        p = last
        curr = len(len_list)
        len_list.append(len_list[p] + 1)
        link.append(0)
        nexts.append({})
        while p != -1 and c not in nexts[p]:
            nexts[p][c] = curr
            p = link[p]
        if p == -1:
            link[curr] = 0
        else:
            q = nexts[p][c]
            if len_list[p] + 1 == len_list[q]:
                link[curr] = q
            else:
                clone = len(len_list)
                len_list.append(len_list[p] + 1)
                link.append(link[q])
                nexts.append(nexts[q].copy())
                while p != -1 and nexts[p][c] == q:
                    nexts[p][c] = clone
                    p = link[p]
                link[q] = link[curr] = clone
        last = curr
    return nexts, len_list

def longest_common_substring(s1, s2):
    nexts, len_list = build_suffix_automaton_basic(s1)
    v = 0
    l = 0
    best_len = 0
    best_pos = 0

    for i in range(len(s2)):
        c = s2[i]
        while v != 0 and c not in nexts[v]:
            v = link[v]
            l = len_list[v]
        if c in nexts[v]:
            v = nexts[v][c]
            l += 1
        if l > best_len:
            best_len = l
            best_pos = i
    return s2[best_pos - best_len + 1: best_pos + 1]

# 예제
print(longest_common_substring("xabxac", "abcabxabcd"))  # 출력: abxa

---

📚 마무리 요약

기능 알고리즘 설명

중복 포함 부분 문자열 개수	Suffix Automaton + 크기 전파	상태 간 길이 차이 × 등장 횟수
가장 긴 공통 부분 문자열	Suffix Automaton + 추적	한 문자열로 자동자 생성 → 다른 문자열로 longest path 탐색

Suffix Automaton 과 KMP