Open devLupin opened 11 months ago
const int ROOT = 1; // 루트
int unused = 2; // 사용된 정점의 번호
const int MX = 10000 * 500 + 5; // 문자의 등장횟수(+5는 배열 여유를 둔 것)
bool chk[MX] // 문자열의 끝이다 라는 표시
int nxt[MX][26]; // 자식 정점 번호, 알파벳이라는 가정(26개)
// O(1)에 탐색이 가능하지만 메모리 측면에서 조금 비효율적임.
for(int i=0; i<MX; i++)
fill(nxt[i], nxt[i]+26, -1); // 돌다가 -1을 만나면 해당 자식 정점이 없다는 뜻
nxt[5][4] = 6; // 5번 위치의 자식은 4번째 알파벳이고(E가 4번째 알파벳) 6번 노드에 저장되어 있다.
nxt[5][24]=7; // 5번 위치의 다른 자식은 24번째 알파벳이고(Y = 24번째) 7번 노드에 저장되어 있다.
nxt[5][나머지] = -1
// chk배열
// 초록색으로 표시된 게 단어의 끝이라는 의미이고
// 해당 부분만 true, 그 외에는 false이다.
void insert(string &s) {
int cur = ROOT; // init
for(auto c : s) {
if(nxt[cur][c2i(c)] == -1) // 자식 정점이 없으니
nxt[cur][c2i(c)] = unused++; // 새로운 정점 번호 부여
cur = nxt[cur][c2i(c)]; // 이후, 현재 보고 있는 정점 이동
}
chk[cur] = true;
bool find(string& s) {
int cur = ROOT;
for(auto c : s) {
if(nxt[cur][c2i(c)] == -1)
return false;
cur = nxt[cur][c2i(c)];
}
return chk[cur];
}
void erase(string& s) {
int cur = ROOT;
for(auto c : s) {
if(nxt[cur][c2i(c)] == -1) // 트라이에 없음.
return;
cur = nxt[cur][c2i(c)];
}
chk[cur] = false;
}
S
를 삽입/탐색/삭제할 때 $O(|S|)$4x글자의 종류
배 만큼 더 사용문자열이 있다
는 표시만 제거한다.