fork download
copy 
  1. #include <string>
  2. #include <iostream>
  3.  
  4. namespace no_stl
  5. {
  6.     constexpr std::size_t MAX_UNIQUE = 1024*128 ;
  7.     std::string uniques[MAX_UNIQUE] ;
  8.     std::size_t n_unique = 0 ;
  9.  
  10.     bool is_unique( const std::string& str )
  11.     {
  12.         for( std::size_t i = 0 ; i < n_unique ; ++i )
  13.             if( uniques[i] == str ) return false ;
  14.         return true ;
  15.     }
  16.  
  17.     std::size_t insert_unique( const std::string& str )
  18.     {
  19.         if( is_unique(str) && n_unique<MAX_UNIQUE )
  20.         {
  21.             uniques[n_unique] = str ;
  22.             ++n_unique ;
  23.         }
  24.         return n_unique ;
  25.     }
  26.  
  27.     std::size_t distinct_substrings( const std::string& str )
  28.     {
  29.         if( !str.empty() )
  30.         {
  31.             for( std::size_t i = 0 ; i <= str.size() ; ++i )
  32.                 insert_unique( str.substr(0,i) ) ;
  33.             distinct_substrings( str.substr(1) ) ;
  34.         }
  35.         return n_unique ;
  36.     }
  37. }
  38.  
  39. namespace use_stdlib
  40. {
  41.     template < typename SET >std::size_t distinct_substrings( SET& set,
  42.                                                        const std::string& str )
  43.     {
  44.         if( !str.empty() )
  45.         {
  46.             for( std::size_t i = 0 ; i <= str.size() ; ++i )
  47.                 set.insert( str.substr(0,i) ) ;
  48.             distinct_substrings( set, str.substr(1) ) ; // O(N*N)
  49.         }
  50.         return set.size() ;
  51.     }
  52. }
  53.  
  54. #include <set>
  55.  
  56. int main()
  57. {
  58.     {
  59.         using namespace no_stl ;
  60.         const std::string str = "abababc" ;
  61.  
  62.         distinct_substrings(str) ;
  63.         std::cout << "#distinct substrings of '" << str << "' " << n_unique << '\n' ;
  64.         for( std::size_t i = 0 ; i < n_unique ; ++i )
  65.             std::cout << "'" << uniques[i] << "'\n" ;
  66.     }
  67.  
  68.     std::cout << "\n---------------------------\n" ;
  69.  
  70.     {
  71.         std::set<std::string> set ; // or use std::unordered_set
  72.         const std::string str = "abababc" ;
  73.  
  74.         use_stdlib::distinct_substrings( set, str ) ;
  75.         std::cout << "#distinct substrings of '" << str << "' " << set.size() << '\n' ;
  76.         for( const auto& s : set ) std::cout << "'" << s << "'\n" ;
  77.     }
  78. }
  79.  
Success #stdin #stdout 0s 3544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#distinct substrings of 'abababc' 19
''
'a'
'ab'
'aba'
'abab'
'ababa'
'ababab'
'abababc'
'b'
'ba'
'bab'
'baba'
'babab'
'bababc'
'ababc'
'babc'
'abc'
'bc'
'c'

---------------------------
#distinct substrings of 'abababc' 19
''
'a'
'ab'
'aba'
'abab'
'ababa'
'ababab'
'abababc'
'ababc'
'abc'
'b'
'ba'
'bab'
'baba'
'babab'
'bababc'
'babc'
'bc'
'c'
https://ideone.com/aOEVhB
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!