Pagini recente » Rezultatele filtrării | Cod sursa (job #1894182) | Rezultatele filtrării | Istoria paginii runda/simulare-cartita-51b/clasament | Cod sursa (job #1729944)
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXLG = 20;
const int ALPHALEN = 26;
struct node
{
int wordsCount;
int prefixCount;
char currentWord[MAXLG+1];
char letter;
node* next[ALPHALEN+1];
};
node* root = NULL;
void initNode(node** x)
{
*x = new(node);
(*x)->wordsCount = 0;
(*x)->prefixCount = 0;
for(int i = 0; i < ALPHALEN; i++)
((*x)->next)[i] = NULL;
}
void addWord(int pos, char* word, node** x)
{
if(pos == strlen(word))
return;
if(*x == NULL)
initNode(x);
(*x)->letter = word[pos];
(*x)->prefixCount++;
if(pos == strlen(word)-1)
{
strcpy((*x)->currentWord,word);
(*x)->wordsCount++;
}
addWord(pos+1,word,&(((*x)->next)[word[pos+1]-'a']));
}
void deleteWord(int pos, char* word, node** x)
{
(*x)->prefixCount--;
if(pos == strlen(word) - 1)
(*x)->wordsCount--;
else
deleteWord(pos+1,word,&(((*x)->next)[word[pos+1]-'a']));
}
int getWordCount(int pos, char* word, node** x)
{
if(*x == NULL)
return 0;
else
if(pos == strlen(word) - 1)
return (*x)->wordsCount;
else
getWordCount(pos+1,word,&(((*x)->next)[word[pos+1]-'a']));
}
void parcurgere(node* x)
{
if(strlen(x->currentWord) != 0)
printf("%s %d %d\n",x->currentWord,x->wordsCount,x->prefixCount);
for(int i = 0; i < ALPHALEN; i++)
if((x->next)[i] != NULL)
parcurgere((x->next)[i]);
}
int len = 0;
void getMaxLenPrefix(int pos, char* word, node** x)
{
if(pos == strlen(word) || (*x) == NULL)
return;
if((*x)->prefixCount >= 1)
len = max(len, pos + 1);
getMaxLenPrefix(pos+1,word,&(((*x)->next)[word[pos+1]-'a']));
}
int main()
{
freopen("trie.in","r",stdin);
freopen("trie.out","w",stdout);
initNode(&root);
int type, x;
char w[MAXLG+1];
while(scanf("%d",&type) == 1)
{
scanf("%s",w);
switch(type)
{
case 0:
addWord(0,w,&(((root)->next)[w[0]-'a']));
break;
case 1:
deleteWord(0,w,&(((root)->next)[w[0]-'a']));
break;
case 2:
x = getWordCount(0,w,&(((root)->next)[w[0]-'a']));
printf("%d\n",x);
break;
case 3:
len = 0;
getMaxLenPrefix(0,w,&(((root)->next)[w[0]-'a']));
printf("%d\n",len);
break;
}
}
return 0;
}