접미사 트라이(Trie)를 활용한 문자열 패턴 검색 알고리즘

주어진 텍스트에서 만들 수 있는 모든 접미사(suffix)를 생성해 하나의 트리 구조로 구성할 수 있습니다. 여기서 핵심은, 텍스트 안에 등장하는 모든 패턴은 반드시 텍스트의 어떤 접미사의 접두사(prefix)가 된다는 성질입니다. 따라서 모든 접미사로 트라이(Trie)를 미리 만들어 두면, 임의의 부분 문자열을 선형 시간에 찾아낼 수 있습니다.

각 접미사는 문자열 종료 기호로 끝납니다. 탐색은 루트 노드에서 시작하여, 자식으로 이어지는 경로가 있으면 계속 앞으로 진행하고, 더 이상 경로가 없으면 해당 패턴이 존재하지 않는다고 판단합니다.

이 알고리즘의 시간 복잡도는 O(m + k)입니다. 여기서 m은 문자열의 길이, k는 텍스트 안에서 패턴이 나타나는 빈도를 의미합니다.

입력과 출력

입력:
메인 문자열: "ABAAABCDBBABCDDEBCABC", 패턴: "ABC"
출력:
패턴 발견 위치: 4
패턴 발견 위치: 10
패턴 발견 위치: 18

알고리즘

이 알고리즘은 트라이 노드(trie node)라고 하는 특수한 노드를 사용합니다. 트라이 노드는 자신에게 연결된 모든 접미사의 인덱스와, 다른 트라이 노드의 주소를 링크 형태로 함께 보관합니다.

createTrie(root: trieNode, text)

입력: trieNode 타입의 루트 노드

출력: 메인 문자열로부터 만들어진 접미사 트리

시작
    i := 0부터 텍스트 길이까지 반복
        i번째 위치부터 끝까지의 부분 문자열을 접미사로 삼아, 인덱스 i와 함께 트라이에 추가
    반복 종료
끝

findPat(pattern, node)

입력: 찾고자 하는 패턴, 그리고 하위 접미사 서브트리를 검사하는 데 사용할 노드

출력: 패턴이 발견된 인덱스 목록

시작
    패턴의 크기가 0이면
        노드의 suffIndex 반환
    node.suff[pattern[0]] ≠ φ 이면
        node.suff[pattern[0]].findPat(패턴의 1번째 문자부터 끝까지의 부분 문자열) 반환
    아니면
        φ 반환
끝

searchPat(pattern)

입력: 검색할 패턴

출력: 패턴이 발견된 텍스트 내 인덱스 목록

시작
    res를 목록(list)으로 정의
    res := findPat(pattern)

    res ≠ φ 이면
        patLen := 패턴의 길이
        res 목록 전체를 순회하며
            패턴이 발견된 모든 인덱스 출력
끝

C++ 구현 예제

#include<iostream>
#include<list>
#define MAXCHAR 256
using namespace std;

class trieNode {      //모든 접미사를 저장하는 노드
    private:
        trieNode *suff[MAXCHAR];
        list<int> *suffIndex;
    public:
        trieNode() {
            suffIndex = new list<int>;
            for (int i = 0; i < MAXCHAR; i++)
                suff[i] = NULL;      //초기에는 자식 노드 없음
        }

        void addSuffix(string suffix, int sIndex);
        list<int>* searchPattern(string pat);
};

void trieNode::addSuffix(string suffix, int sIndex) {
    suffIndex->push_back(sIndex);      //먼저 인덱스를 저장

    if (suffix.size() > 0) {
        char cIndex = suffix[0];
        if (suff[cIndex] == NULL)      //해당 문자의 서브트리가 없으면
            suff[cIndex] = new trieNode();   //새 노드 생성
        suff[cIndex]->addSuffix(suffix.substr(1), sIndex+1);   //다음 접미사 처리
    }
}

list<int>* trieNode::searchPattern(string pattern) {
    if (pattern.size() == 0)
        return suffIndex;
    if (suff[pattern[0]] != NULL)
        return (suff[pattern[0]])->searchPattern(pattern.substr(1));   //다음 노드로 이동
    else
        return NULL;      //더 이상 이동할 노드가 없는 경우
}

class trieSuffix {      //모든 접미사를 위한 트라이
    trieNode root;
    public:
        trieSuffix(string mainString) {      //접미사를 추가하며 트라이 생성
            for (int i = 0; i < mainString.length(); i++)
                root.addSuffix(mainString.substr(i), i);
        }

    void searchPat(string pattern, int *locArray, int *index);
};

void trieSuffix::searchPat(string pattern, int *locArray, int *index) {
    list<int> *res = root.searchPattern(pattern);
    //인덱스 목록이 비어 있는지 확인
    if (res != NULL) {
        list<int>::iterator it;
        int patLen = pattern.length();
        for (it = res->begin(); it != res->end(); it++) {
            (*index)++;
            locArray[(*index)] = *it - patLen;
        }
    }
}

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

    trieSuffix trie(mainString);
    trie.searchPat(pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "패턴 발견 위치: " << locArray[i]<<endl;
    }

}

실행 결과

패턴 발견 위치: 4
패턴 발견 위치: 10
패턴 발견 위치: 18

참고: 장단점

접미사 트라이는 전처리를 마친 뒤에는 질의 속도가 매우 빠르다는 장점이 있지만, 모든 접미사를 개별적으로 저장하기 때문에 공간 복잡도가 최대 O(n²)까지 커질 수 있습니다. 그래서 입력 문자열이 아주 긴 실무 환경에서는 간선을 압축한 압축 접미사 트리(compressed suffix tree)나 접미사 배열(suffix array) 같은 자료구조가 더 효율적인 선택이 되곤 합니다.