Pagini recente » Borderou de evaluare (job #2934824) | Istoria paginii utilizator/adiailie | Cod sursa (job #1600556)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("trie.in");
ofstream fout("trie.out");
#define CH(c)(c - 'a')
class Trie {
public:
static const int ALPHA = 26;
Trie *son[ALPHA];
int areHere, endsHere;
Trie() {
areHere = endsHere = 0;
memset(son, 0, sizeof(son));
}
~Trie() {
for (int i = 0; i < ALPHA; ++i) {
if (son[i] != NULL) {
delete son[i];
}
}
}
// void insert(char *s) {
// Trie *node = this;
// ++node-> areHere;
// for (int i = 0; s[i]; ++i) {
// int x = s[i] - 'a';
// if (!node->son[x]) {
// node->son[x] = new Trie();
// }
// node = node->son[x];
// ++node->areHere;
// }
// ++node->endsHere;
// }
// void remove(char *s) {
// Trie *node = this;
// --node->areHere;
// for (int i = 0; s[i]; ++i) {
// int x = s[i] - 'a' ;
// if (!node->son[x]) {
// return;
// }
// node = node->son[x];
// --node->areHere;
// }
// --node->endsHere;
// if (node->endsHere < 0 )
// node -> endsHere = 0;
// }
// int search(char *s) {
// Trie *node = this;
// for (int i = 0; s[i]; ++i) {
// int x = s[i] - 'a' ;
// if (!node->son[x]) {
// return 0;
// }
// node =node->son[x];
// }
// return node->endsHere;
// }
// int lcp(char *s) {
// Trie *node = this;
// int i;
// for (i = 0; s[i]; ++i) {
// int x = s[i] - 'a' ;
// if (!node->son[x] ) {
// return i;
// }
// node = node->son[x];
// if (!node->areHere) {
// return i;
// }
// }
// return i;
// }
};
void insert(Trie *node ,char *s) {
++node-> areHere;
for (int i = 0; s[i]; ++i) {
int x = s[i] - 'a';
if (!node->son[x]) {
node->son[x] = new Trie();
}
node = node->son[x];
++node->areHere;
}
++node->endsHere;
}
void remove(Trie *node ,char *s) {
--node->areHere;
for (int i = 0; s[i]; ++i) {
int x = s[i] - 'a' ;
if (!node->son[x]) {
return;
}
node = node->son[x];
--node->areHere;
}
--node->endsHere;
if (node->endsHere < 0 )
node -> endsHere = 0;
}
int search(Trie *node ,char *s) {
for (int i = 0; s[i]; ++i) {
int x = s[i] - 'a' ;
if (!node->son[x]) {
return 0;
}
node =node->son[x];
}
return node->endsHere;
}
int lcp(Trie *node ,char *s) {
int i;
for (i = 0; s[i]; ++i) {
int x = s[i] - 'a' ;
if (!node->son[x] ) {
return i;
}
node = node->son[x];
if (!node->areHere) {
return i;
}
}
return i;
}
int main() {
Trie *T = new Trie();
int op;
string word;
int result;
while (fin >> op) {
fin >> word;
char *s = (char * )word.c_str();
switch(op) {
case 0:
insert(T,s);
break;
case 1:
remove(T,s);
break;
case 2:
fout << search(T,s) << '\n';
break;
case 3:
fout << lcp(T,s) << '\n';
break;
default:
break;
}
}
delete T;
fin.close();
fout.close();
return 0;
}