#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" ;
    }
}