Pagini recente » Cod sursa (job #292338) | Cod sursa (job #1644189) | Cod sursa (job #2949449) | Cod sursa (job #866630) | Cod sursa (job #766683)
Cod sursa(job #766683)
#include <fstream>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
struct trie {
int words;
int prefixes;
struct trie* edges[26];
};
typedef struct trie Trie;
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)
{
vertex->edges[next_pos] = (Trie*) calloc (1, sizeof(Trie));
}
add (vertex->edges[next_pos], word, ++position);
}*/
int next;
Trie* copy = vertex;
while (word.length() != position)
{
copy->prefixes++;
next = word[position] % 26;
if (copy->edges[next] == NULL)
{
copy->edges[next] = (Trie*) calloc (1, sizeof(Trie));
}
copy = copy->edges[next];
position++;
}
copy->words++;
}
void remove (Trie* vertex, string word, int position)
{
int k;
if(word.length() != position)
{
vertex->prefixes--;
k = word[position]%26;
remove (vertex->edges[k], word, ++position);
if (vertex->edges[k]->prefixes == 0 && vertex->edges[k]->words == 0)
{
free(vertex->edges[k]);
vertex->edges[k] = NULL;
}
}
else
{
vertex->words--;
}
}
void print (Trie* vertex, string word, int position)
{
if (word.length() == position)
{
printf("%d\n", vertex->words);
}
else
{
int next_pos = word[position]%26;
if (vertex->edges[next_pos] != NULL)
{
print(vertex->edges[next_pos], word, ++position);
}
else
{
printf ("0\n");
}
}
}
void max_prefix(Trie* vertex, string word, int position)
{
if (word.length() == position)
{
printf("%d\n",position);
}
else
{
if (vertex->prefixes == 0)
{
if (vertex->words == 0)
{
printf("%d\n",position - 1);
}
else
{
printf("%d\n", position);
}
}
else
{
int next_pos = word[position] % 26;
if (vertex->edges[next_pos] != NULL)
{
max_prefix (vertex->edges[next_pos], word, ++position);
}
else
{
printf("%d\n",position);
}
}
}
}
int main() {
int x;
char text[21];
freopen("trie.in", "r", stdin);
freopen("trie.out","w",stdout);
Trie* firstVertex;
firstVertex = (Trie*) calloc (1,sizeof(Trie));
while (scanf("%d %s\n",&x, text)!= EOF)
{
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;
}
}
}