Advertisement
NonWhite

Trie [Struct]

Aug 2nd, 2012
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <cstring>
  5. #include <set>
  6. #include <map>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <stack>
  11. #include <sstream>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <cctype>
  15. #define clr( x , y ) memset( x ,y , sizeof x )
  16. #define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
  17. #define mp make_pair
  18. #define TAM 100
  19. #define MOD 1000000007
  20. #define debug( x ) cout << #x << " = " << x << endl
  21. #define f(i,n) for(int i = 0 ; i < n ; i++)
  22. #define ff(i,a,b) for(int i = a ; i < b ; i++)
  23. #define all( x ) x.begin() , x.end()
  24. #define ral( x ) x.rbegin() , x.rend()
  25.  
  26. using namespace std ;
  27.  
  28. typedef pair<int,int> ii ;
  29. typedef pair<ii,ii> pii ;
  30. typedef long long ll ;
  31. typedef long double ld ;
  32.  
  33. string alpha ;
  34.  
  35. struct Trie{
  36.     Trie * next[ 300 ] ;
  37.     int words ;
  38.     int prefix ;
  39.  
  40.     Trie(){
  41.         init() ;
  42.     }
  43.  
  44.     void init(){
  45.         for(int i = 0 ; i < 300 ; i++) next[ i ] = NULL ;
  46.         words = prefix = 0 ;
  47.         alpha = "" ;
  48.     }
  49.  
  50.     char toDict( char c ){
  51.         if( !alpha.find( c ) ) alpha += c ;
  52.         return c ;
  53.     }  
  54.  
  55.     void add( string S ){
  56.         Trie * nodo = this ;
  57.         for(int i = 0 ; i < S.size() ; i++){
  58.             char c = toDict( S[ i ] ) ;
  59.             if( nodo->next[ c ] == NULL ) nodo->next[ c ] = new Trie ;
  60.             nodo->prefix++ ;
  61.             nodo = nodo->next[ c ] ;
  62.         }
  63.         nodo->words++ ;
  64.         nodo->prefix++ ;
  65.         printf("\tAñadido \"%s\"\n" , S.c_str() ) ;
  66.     }
  67.  
  68.     int countWords( string S ){
  69.         Trie * nodo = this ;
  70.         for(int i = 0 ; i < S.size() ; i++){
  71.             char c = S[ i ] ;
  72.             if( nodo->next[ c ] == NULL ) return 0 ;
  73.             nodo = nodo->next[ c ] ;
  74.         }
  75.         return nodo->words ;
  76.     }
  77.  
  78.     int countPrefix( string S ){
  79.         Trie * nodo = this ;
  80.         for(int i = 0 ; i < S.size() ; i++){
  81.             char c = S[ i ] ;
  82.             if( nodo->next[ c ] == NULL ) return 0 ;
  83.             nodo = nodo->next[ c ] ;
  84.         }
  85.         return nodo->prefix ;
  86.     }
  87.  
  88. } T ;
  89.  
  90. int main(){
  91.  
  92.     T.init() ;
  93.  
  94.     char c , S[ TAM ] ;
  95.     while( scanf("%c %s" , &c , S ) == 2 ){
  96.         cin.ignore() ;
  97.         if( c == 'A' )
  98.             T.add( S ) ;
  99.         else if( c == 'C' )
  100.             printf("#pal( %s ) = %d\n" , S , T.countWords( S ) ) ;
  101.         else if( c == 'P' )
  102.             printf("#prefix( %s ) = %d\n" , S , T.countPrefix( S ) ) ;
  103.     }
  104.     return 0 ;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement