#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int NumberOfTests, NumberOfWords, Index, AlphabetSize, WordLen;
char Alphabet[27], Word[1001];
class Node
{
public:
Node *Next[26];
int WordCounter;
Node();
};
Node::Node()
{
for(int i=0; i<26; ++i) Next[i]=NULL;
WordCounter=0;
}
bool Search(int LastLetter, int CurrentLetter, Node *CurrentNode)
{
if(CurrentLetter>LastLetter) return true;
CurrentNode=CurrentNode->Next[Word[CurrentLetter]-97];
if(CurrentNode!=NULL) Search(LastLetter, CurrentLetter+1, CurrentNode);
else return false;
}
void Insert(int LastLetter, int CurrentLetter, Node **CurrentNode)
{
if(CurrentLetter>LastLetter)
{
(*CurrentNode)->WordCounter++;
return;
}
CurrentNode=&(*CurrentNode)->Next[Word[CurrentLetter]-97];
if((*CurrentNode)==NULL) (*CurrentNode)=new Node();
Insert(LastLetter, CurrentLetter+1, CurrentNode);
}
void Show(string Temp, Node *CurrentNode)
{
while(CurrentNode->WordCounter--) cout<<Temp<<endl;
for(int Index=0; Index<AlphabetSize; ++Index)
{
if(CurrentNode->Next[Alphabet[Index]-97]!=NULL) Show(Temp+Alphabet[Index], CurrentNode->Next[Alphabet[Index]-97]);
}
}
void Delete(Node **CurrentNode)
{
for(int Index=0; Index<AlphabetSize; ++Index)
{
if((*CurrentNode)->Next[Alphabet[Index]-97]!=NULL) Delete(&(*CurrentNode)->Next[Alphabet[Index]-97]);
}
delete *CurrentNode;
}
int main()
{
ios_base::sync_with_stdio(0);
string Temp="";
scanf("%d", &NumberOfTests);
while(NumberOfTests--)
{
Node *Root=new Node();
gets(Alphabet);
AlphabetSize=strlen(Alphabet);
scanf("%d", &NumberOfWords);
for(Index=0; Index<NumberOfWords; ++Index)
{
gets(Word);
WordLen=strlen(Word)-1;
Insert(WordLen, 0, &Root);
}
Show(Temp, Root);
Delete(&Root);
cout<<endl;
}
return 0;
}
How can I improve time result? This trie implementation gets 11.70. I've also sent another version, using vector of shorts to store following nodes for each one and sorting it with stl sort (thanks to that I could save some time on checking array of following nodes), but it turned out to be much worse - 15s.
Shall I use radix sort on array of pointers to strings instead?