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;
}
}
};