Pagini recente » Cod sursa (job #2325266) | Cod sursa (job #1743142) | Cod sursa (job #1392217) | Cod sursa (job #2117157) | Cod sursa (job #582413)
Cod sursa(job #582413)
#include <fstream>
#include <cstdlib>
#define N_MAX 29
using namespace std;
typedef string::const_iterator siter;
class Trie
{
bool isRoot;
int countApp;
int countSet;
Trie *isSet[N_MAX];
public :
Trie() : isRoot(true), countApp(0), countSet(0)
{
for( int i=0; i < N_MAX; ++i )
isSet[i]=NULL;
}
void Add( siter it, const siter& iend )
{
if( it >= iend )
{
++countApp;
return;
}
int x=*it-'a';
if( !isSet[x] )
isSet[x]=new Trie(), isSet[x]->isRoot=false, ++countSet;
isSet[x]->Add( it+1, iend );
}
bool Delete( siter it, const siter& iend )
{
if( it >= iend )
{
--countApp;
countApp=countApp < 0 ? 0 : countApp;
if( 0 == countApp && 0 == countSet )
return true;
return false;
}
int x=*it-'a';
if( isSet[x]->Delete( it+1, iend ) )
{
isSet[x]=NULL;
--countSet;
}
if( !isRoot && 0 == countSet )
{
delete this;
return true;
}
return false;
}
int CountApp( siter it, const siter& iend )
{
if( it >= iend )
return countApp;
int x=*it-'a';
if( !isSet[x] )
return 0;
return isSet[x]->CountApp( it+1, iend );
}
int LCP( siter it, const siter& iend )
{
if( it >= iend )
return 0;
int x=*it-'a';
if( !isSet[x] )
return 0;
return 1+isSet[x]->LCP( it+1, iend );
}
} *r=new Trie();
int main()
{
int op;
string s;
ifstream in( "trie.in" );
ofstream out( "trie.out" );
while( in>>op>>s )
{
switch(op)
{
case 0 : r->Add( s.begin(), s.end() ); break;
case 1 : r->Delete( s.begin(), s.end() ); break;
case 2 : out<<r->CountApp( s.begin(), s.end() )<<'\n'; break;
case 3 : out<<r->LCP( s.begin(), s.end() )<<'\n'; break;
}
}
return EXIT_SUCCESS;
}