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

Answer 2

First, you should pay attention about code indent. Then, I don't look your code, I wrote some code to achieve your aim, as follow:

void generateSubstrings(string s, int num, vector<string> &sta)
{
    if (num == s.size())
        return;

    auto b = begin(s) + num;

    string temp = "";
    temp += *b;
    sta.push_back(temp);
    b++;
    while (b != end(s))
    {

        temp += *b;
        sta.push_back(temp);
        b++;

    }
    generateSubstrings(s, num + 1, sta);
}

Answer 3

Here's an answer using Python. It prints the correct result for "rum", but for "rumm" it prints two "m" substrings for obvious reasons:

def substrings(s):
  result = []
  if len(s) == 0:
    result.append("")
  if len(s) > 0:
    result += substrings(s[1:])
  for n in range(1,len(s)+1):
    result.append(s[0:n])
  return result

print substrings("rum")

print substrings("rumm")

The idea of the algorithm is the following: for "rum", the substrings are the substrings of "um" followed by "r", "ru" and "rum". For "um", the substrings are the substrings of "m" followed by "u" and "um". For "m", the substrings are the substrings of "" followed by "m". For "", the substrings are simply "". So, the final list is "", "m", "u", "um", "r", "ru", "rum".

Although this isn't C++, you should be able to translate the code to C++. But that may not necessarily be what you want as "rumm" has two "m" substrings. If you think that "rumm" should have only one "m" substring, please leave a comment and I'll post another answer.