Pagini recente » Borderou de evaluare (job #808654) | Cod sursa (job #2402679)
#define DM 21
#define DN 27
#include <fstream>
using namespace std;
ifstream fi ("trie.in");
ofstream fo ("trie.out");
char cuv[DM];
short int q;
struct trie {
short int ending, nrSons;
trie * sons[DN];
trie() {
ending = nrSons = 0;
for (short int i = 0; i < DN; ++i)
sons[i] = 0;
}
};
trie * root = new trie();
void addWord(char * c, trie * crt) {
if (*c == '\0') {
++(crt->ending);
return;
}
if (crt->sons[*c-'a'] == 0) {
crt->sons[*c-'a'] = new trie();
++(crt->nrSons);
}
addWord(c + 1, crt->sons[*c-'a']);
}
bool deleteWord(char * c, trie * crt) {
if (*c == '\0') {
--(crt->ending);
if (!(crt->ending) && !(crt->nrSons) && crt != root) {
delete crt;
return 1;
}
return 0;
}
if (deleteWord(c + 1, crt->sons[*c-'a'])) {
--(crt->nrSons);
crt->sons[*c-'a'] = 0;
if (!(crt->ending) && !(crt->nrSons) && crt != root) {
delete crt;
return 1;
}
}
return 0;
}
short int findWord(char * c, trie * crt) {
if (*c == '\0')
return (crt->ending);
if (crt->sons[*c-'a'] == 0)
return 0;
return findWord(c + 1, crt->sons[*c-'a']);
}
short int maxPrefix(char * c, trie * crt) {
if (*c == '\0')
return 0;
if (crt->sons[*c-'a'] == 0)
return 0;
return 1 + maxPrefix(c + 1, crt->sons[*c-'a']);
}
int main() {
while (fi >> q) {
fi >> cuv;
switch (q) {//ba, jur ca nu-s gay, vreau numai sa vad cum merge switch
case 0:
addWord(cuv, root);
break;
case 1:
deleteWord(cuv, root);
break;
case 2:
fo << findWord(cuv, root) << '\n';
break;
case 3:
fo << maxPrefix(cuv, root) << '\n';
break;
default:
fo << "ba ce pula mea";
}
}
return 0;
}