Suffix Tree 자체 구현


작성일 : 2017-06-22 20:39:23
조회수 : 1191


본문

Suffix Tree는 접미사 배열로 압축하는 버전이 아닌, 문자열 자체로 구축하는 방식의 Tree입니다.

최적의 솔루션으로 되지 않았을 수도 있습니다.

root를 구분하기 위해 $라는 문자열로 구분을 하였습니다.(즉, 아무것도 없는 빈 문자열도 하나의 접미사로 취급을 하였습니다.)

#define MAX_LEN 50
class SuffixTree
{
public:
    char suffix[MAX_LEN];
    bool selected;
    SuffixTree *child[MAX_LEN], *parent;
    SuffixTree(){ selected = false; suffix[0] = 0; for (int i = 0; i < MAX_LEN; i++)child[i] = NULL; }
    SuffixTree(char c[])
    {
        int l = strlen(c);
        selected = false;
        for (int i = 0; i < 30; i++)child[i] = NULL;
        for(int i = 0; i < l; i++) suffix[i] = c[i];
        suffix[l] = 0;
    }
    int length() { return strlen(suffix); }
    int getMatchedLength(char sub[])
    {
        int l = strlen(sub), r = this->length(), k = (l <= r ? l : r), ret = 0;
        for (int i = 0; i < k; i++)
        {
            if (sub[i] == '$') continue;
            if (suffix[i] != sub[i]) break;
            ret++;
        }
        return ret;
    }
    void split(int pos)
    {
        SuffixTree *temp = new SuffixTree();
        //0~pos-1까지 temp에 옮긴다.
        for (int i = 0; i < pos; i++)
            temp->suffix[i] = suffix[i];
        temp->suffix[pos] = 0;
        //pos~len까지 땡긴다.
        int l = this->length();
        for (int i = pos; i < l; i++) suffix[i - pos] = suffix[i];
        suffix[l - pos] = 0;
        //부모의 연결관계 변경
        for (int i = 0; i <= 26; i++)
        {
            if (parent->child[i] == this)
            {
                int tpos = getp(suffix[0]);
                parent->child[i] = temp;
                temp->parent = parent;
                temp->child[tpos] = this;
                this->parent = temp;
                break;
            }
        }
        
    }
    void addNode(char txt[])
    {
        int l = strlen(txt);
        if (l == 1)    //종료문자열만 들어온 경우 그냥 추가
        {
            int pos = getp(txt[0]);
            child[pos] = new SuffixTree(txt);
            child[pos]->parent = this;
            return;
        }
        bool f = false;
        for (int i = 0; i <= 26; i++)
        {
            if (!child[i]) continue;
            int ml = child[i]->getMatchedLength(txt);
            if (ml)
            {
                f = true;
                if (ml != child[i]->length())    //나뉜적이 없는 패턴인 경우 split진행
                    child[i]->split(ml);
                child[i]->addNode(txt + ml);
                break;
            }
        }
        if (!f)
        {
            int pos = getp(txt[0]);
            child[pos] = new SuffixTree(txt);
            child[pos]->parent = this;
        }
    }
    
};

Suffix Tree 자체 구현 - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.