fork download
  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
stdin
Standard input is empty
stdout
#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'