#include <string>
#include <iostream>
namespace no_stl
{
constexpr std::size_t MAX_UNIQUE = 1024*128 ;
std::string uniques[MAX_UNIQUE] ;
std::size_t n_unique = 0 ;
bool is_unique( const std::string& str )
{
for( std::size_t i = 0 ; i < n_unique ; ++i )
if( uniques[i] == str ) return false ;
return true ;
}
std::size_t insert_unique( const std::string& str )
{
if( is_unique(str) && n_unique<MAX_UNIQUE )
{
uniques[n_unique] = str ;
++n_unique ;
}
return n_unique ;
}
std::size_t distinct_substrings( const std::string& str )
{
if( !str.empty() )
{
for( std::size_t i = 0 ; i <= str.size() ; ++i )
insert_unique( str.substr(0,i) ) ;
distinct_substrings( str.substr(1) ) ;
}
return n_unique ;
}
}
namespace use_stdlib
{
template < typename SET >std::size_t distinct_substrings( SET& set,
const std::string& str )
{
if( !str.empty() )
{
for( std::size_t i = 0 ; i <= str.size() ; ++i )
set.insert( str.substr(0,i) ) ;
distinct_substrings( set, str.substr(1) ) ; // O(N*N)
}
return set.size() ;
}
}
#include <set>
int main()
{
{
using namespace no_stl ;
const std::string str = "abababc" ;
distinct_substrings(str) ;
std::cout << "#distinct substrings of '" << str << "' " << n_unique << '\n' ;
for( std::size_t i = 0 ; i < n_unique ; ++i )
std::cout << "'" << uniques[i] << "'\n" ;
}
std::cout << "\n---------------------------\n" ;
{
std::set<std::string> set ; // or use std::unordered_set
const std::string str = "abababc" ;
use_stdlib::distinct_substrings( set, str ) ;
std::cout << "#distinct substrings of '" << str << "' " << set.size() << '\n' ;
for( const auto& s : set ) std::cout << "'" << s << "'\n" ;
}
}