Recursive Function that returns all substrings of a string

Question

I need to implement a function in C++,

vector<string> generateSubstrings(string s),

that returns a vector of all substrings of a string. For example, the substrings of the string “rum” are the seven strings

“r”, “ru”, “rum”, “u”, “um”, “m”, “”.

The function has to be recursive and has to return the results as a vector.

Here is my code so far. It's only printing "r", "ru" and "rm". I'm having alot of trouble implementing this function. I've been working on this for the past few hours but I just can't figure out how to get it working as stated, so any help would be appreciated.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> generateSubstrings(string s, int num){ 
    int index = num;
    int SIZE = s.size();

    vector<string> substrings;


    if(index == s.size()){//BASE CASE
        string temp = s.substr(index,1);
        substrings.push_back(temp);
    }
    else{
        for(int i = 0; i < SIZE; ++i){ 
            string temp = s.at(index) + s.substr(i,i);
            substrings.push_back(temp);
        }   
        generateSubstrings(s, num + 1);
    }     
    return substrings; 
} 

int main() { 
    vector<string> vec(20);
    vec = generateSubstrings("rum", 0);


    cout << endl << endl;cout << "PRINTING VECTOR" << endl;

    for ( int i = 0; i<vec.size();++i){
        cout << vec.at(i);
        cout << endl;
    }
    cout << "DONE";
}

Answer 1

In your assignment there is written that the recursive function has to be declared like

vector<string> generateSubstrings(string s),

But you are trying to make another function recursive that declared like

vector<string> generateSubstrings(string s, int num);

So in any case your solution does not satisfy the requirement of the assignment.

The function can look the following way

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> generateSubstrings( std::string s )
{
    if ( s.empty() ) return {};

    std::vector<std::string> v;
    v.reserve( s.size() * ( s.size() + 1 ) / 2 );

    for ( std::string::size_type i = 0; i < s.size(); i++ )
    {
        v.push_back( s.substr( 0, i + 1 ) );
    }

    for ( const std::string &t : generateSubstrings( s.substr( 1 ) ) )
    {
        v.push_back( t );
    }

    return v;
}

int main() 
{
    std::string s( "rum" );

    for ( const std::string &t : generateSubstrings( s ) )
    {
        std::cout << t << std::endl;
    }

    return 0;
}

Its output is

r
ru
rum
u
um
m

If you need also to include an empty string then you should change condition

    if ( s.empty() ) return {};

in appropriate way. For example

   if ( s.empty() ) return { "" };

Also in this case you should write

   v.reserve( s.size() * ( s.size() + 1 ) / 2 + 1 );

Also you can replace the loop in the shown function with method insert. For example

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> generateSubstrings( std::string s )
{
    if ( s.empty() ) return {};

    std::vector<std::string> v;
    v.reserve( s.size() * ( s.size() + 1 ) / 2 );

    for ( std::string::size_type i = 0; i < s.size(); i++ )
    {
        v.push_back( s.substr( 0, i + 1 ) );
    }

    std::vector<std::string> v2 = generateSubstrings( s.substr( 1 ) );

    v.insert( v.end(), v2.begin(), v2.end() );

    return v;
}

int main() 
{
    std::string s( "rum" );

    for ( const std::string &t : generateSubstrings( s ) )
    {
        std::cout << t << std::endl;
    }

    return 0;
}

The program output will be the same as shown above.

Here is a program modification that includes an empty string in the vector.

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> generateSubstrings( std::string s )
{
    if ( s.empty() ) return { "" };

    std::vector<std::string> v;
    v.reserve( s.size() * ( s.size() + 1 ) / 2 + 1 );

    for ( std::string::size_type i = 0; i < s.size(); i++ )
    {
        v.push_back( s.substr( 0, i + 1 ) );
    }

    std::vector<std::string> v2 = generateSubstrings( s.substr( 1 ) );

    v.insert( v.end(), v2.begin(), v2.end() );

    return v;
}

int main() 
{
    std::string s( "rum" );

    for ( const std::string &t : generateSubstrings( s ) )
    {
        std::cout << t << std::endl;
    }

    return 0;
}