Pagini recente » Cod sursa (job #1189274) | Cod sursa (job #2127604) | Cod sursa (job #1315868) | Cod sursa (job #1735617) | Cod sursa (job #766362)
Cod sursa(job #766362)
#include <fstream>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;
struct trie {
int words;
int prefixes;
struct trie* edges[26];
};
ifstream in ("trie.in", ifstream::in);
ofstream out("trie.out", ofstream::out);
typedef struct trie Trie;
void init (Trie **vertex) {
(*vertex) = (Trie*) malloc (sizeof(Trie));
(*vertex)->words = 0;
(*vertex)->prefixes = 0;
for (int i = 0; i < 27; i++) {
(*vertex)->edges[i] = NULL;
}
}
void add (Trie* vertex, string word, int position) {
if (word.length() == position) {
vertex->words++;
}
else
{
vertex->prefixes++;
int next_pos = word[position] % 26;
if (vertex->edges[next_pos] == NULL)
{
init (&vertex->edges[next_pos]);
}
add (vertex->edges[next_pos], word, ++position);
}
}
void remove (Trie* vertex, string word, int position)
{
char k;
if(word.length() != position)
{
vertex->prefixes--;
k = word[position];
remove (vertex->edges[k%26], word, ++position);
}
else
{
vertex->words--;
}
}
void print (Trie* vertex, string word, int position)
{
if (word.length() == position)
{
out << vertex->words << '\n';
}
else
{
int next_pos = word.at((size_t)position)%26;
if (vertex->edges[next_pos] != NULL)
{
print(vertex->edges[next_pos], word, ++position);
}
else
{
out << 0 << '\n';
}
}
}
void max_prefix(Trie* vertex, string word, int position)
{
if (word.length() == position)
{
out << position << '\n';
}
else
{
if (vertex->prefixes == 0)
{
if (vertex->words == 0)
{
out << position - 1 << '\n';
}
else
{
out << position << '\n';
}
}
else
{
int next_pos = word[position] % 26;
if (vertex->edges[next_pos] != NULL)
{
max_prefix (vertex->edges[next_pos], word, ++position);
}
else
{
out << position << '\n';
}
}
}
}
int main() {
int x;
string text;
Trie* firstVertex;
init (&firstVertex);
in >> x >> text;
while (in.eof() == false)
{
switch (x) {
case 0 :
add (firstVertex, text, 0);
break;
case 1 :
remove (firstVertex, text, 0);
break;
case 2 :
print (firstVertex, text, 0);
break;
case 3 :
max_prefix (firstVertex, text, 0);
break;
}
in >> x >> text;
}
}