접미사 배열(Suffix Array) 개념 정리 및 C++ 구현 예제

주어진 문자열에서 만들 수 있는 모든 접미사(suffix)를 구한 뒤, 이를 사전순(lexicographical order)으로 정렬하면 접미사 배열(Suffix Array)을 얻을 수 있습니다. 접미사 배열은 접미사 트리(suffix tree)를 통해서도 만들 수 있는데, 접미사 트리를 DFS(깊이 우선 탐색)로 순회하면 접미사 배열과 동일한 결과를 얻게 됩니다.

접미사 배열을 활용하면 문자열 내에서 특정 패턴을 O(m log n) 시간 복잡도로 효율적으로 검색할 수 있습니다. 여기서 m은 패턴의 길이, n은 원본 문자열의 길이입니다. 또한 이진 탐색(binary search) 방식의 절차를 응용하면 부분 문자열(substring) 검색에도 활용할 수 있습니다.

입력 및 출력 예시

입력:
원본 문자열: "BANANA", 패턴: "NAN"
출력:
패턴 발견 위치: 2

알고리즘

1. fillSuffixArray (text, suffArray)

입력: 원본 문자열

출력: 정렬된 접미사들의 인덱스 배열

Begin
    n := text Length
    define suffix array as allSuffix of size n

    for i := 0 to n-1, do
        allSuffix[i].index := i
        allSuffix[i].suff := substring of text from (i to end)
    done

    sort the allSuffix array
    store indexes of all suffix array in suffArray.
End

이 단계에서는 각 위치 i부터 문자열 끝까지를 하나의 접미사로 만들고, 해당 접미사가 시작되는 인덱스를 함께 저장합니다. 그 후 접미사들을 사전순으로 정렬하여 정렬된 순서대로 인덱스만 추출하면 접미사 배열이 완성됩니다.

2. suffixArraySearch (text, pattern, suffArray)

입력: 원본 문자열, 찾으려는 패턴, 접미사 배열

출력: 패턴이 발견된 위치

Begin
    patLen := size of pattern
    strLen := size of text
    left := 0
    right := strLen -1

    while left <= right, do
        mid := left + (right - left)/2
        tempStr := substring of text from suffArray[mid] to end
        result := compare tempStr and pattern upto pattern length.

        if result = 0, then
            print the location
        if res < 0, then
            right := mid – 1
        else
            left := mid +1
    done
End

검색 단계는 일반적인 이진 탐색과 유사합니다. 중간 인덱스가 가리키는 접미사와 패턴을 비교하여, 패턴이 사전순으로 앞서면 탐색 범위를 왼쪽으로 좁히고, 뒤처지면 오른쪽으로 좁혀 나갑니다.

C++ 구현 예제

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

struct suffix {
    int index;
    string suff;
};

int strCompare(string st1, string st2, int n) {
    int i = 0;
    while(n--) {
        if(st1[i] != st2[i])
            return st1[i] - st2[i];
        i++;
    }
    return 0;
}

bool comp(suffix suff1, suffix suff2) {     //정렬을 위한 두 문자열 비교 함수
    if(suff1.suff<suff2.suff)
        return true;
    return false;
}

void fillSuffixArray(string mainString, int suffArr[]) {
    int n = mainString.size();
    suffix allSuffix[n];     //모든 접미사를 담는 배열

    for(int i = 0; i<n; i++) {
        allSuffix[i].index = i;
        allSuffix[i].suff = mainString.substr(i);     //i번째 위치부터 끝까지
    }

    sort(allSuffix, allSuffix+n, comp);
    for(int i = 0; i<n; i++)
        suffArr[i] = allSuffix[i].index;     //정렬된 접미사들의 인덱스 저장
}

void suffixArraySearch(string mainString, string pattern, int suffArr[], int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int left = 0, right = strLen - 1;     //이진 탐색용 left, right 변수

    while(left <= right) {
        int mid = left + (right - left)/2;
        string tempStr = mainString.substr(suffArr[mid]);
        int result = strCompare(pattern,tempStr, patLen);

        if(result == 0) {     //패턴을 발견한 경우
            (*index)++;
            array[(*index)] = suffArr[mid];
        }

        if(result < 0)
            right = mid -1;
        else
            left = mid +1;
    }
}

int main() {
    string mainString = "BANANA";
    string pattern = "NAN";
    int locArray[mainString.size()];
    int index = -1;

    int suffArr[mainString.size()];
    fillSuffixArray(mainString, suffArr);

    suffixArraySearch(mainString, pattern, suffArr, locArray, &index);
    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i]<<endl;
    }
}

실행 결과

Pattern found at position: 2

"BANANA" 문자열에서 패턴 "NAN"은 인덱스 2의 위치에서 발견됩니다. 이처럼 접미사 배열을 미리 구성해 두면, 동일한 문자열에 대해 여러 번의 패턴 검색을 빠르게 수행할 수 있다는 장점이 있습니다.