рекурсивная функция, которая возвращает все подстроки строки

Question

мне нужно реализовать функцию в C++,

vector<string> generateSubstrings(string s), 

, которая возвращает вектор всех подстрок строки. Например, подстроками строки «ром» являются семь строк

«r», «ru», «rum», «u», «um», «m», «».

Функция должна быть рекурсивной и должна возвращать результаты в виде вектора.

Вот мой код. Это только печать «r», «ru» и «rm». У меня много проблем с выполнением этой функции. Я работаю над этим в течение последних нескольких часов, но я просто не могу понять, как заставить его работать, как указано, поэтому любая помощь будет оценена по достоинству.

#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

В вашем назначении там написано, что рекурсивная функция должна быть объявлена ​​как

vector<string> generateSubstrings(string s), 

Но вы пытаетесь сделать еще одну функцию рекурсивной, что объявленный как

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

Так что в любом случае ваш решение не удовлетворяет требованию назначения.

Функция может выглядеть следующим образом

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

Его выход

r 
ru 
rum 
u 
um 
m 

Если вам необходимо также включить пустую строку, то вы должны изменить условию

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

в надлежащим образом. Например

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

Кроме того, в этом случае вы должны написать

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

Также вы можете заменить петлю в показанной функции с методом вставки.Например,

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

Выход программы будет таким же, как показано выше.

Вот модификация программы, которая включает в себя пустую строку в векторе.

#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

Вот ответ с использованием Python. Он печатает правильный результат для «рома», но для «Rumm» печатает два «М» подстроки по очевидным причинам:

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") 

Идея алгоритма заключается в следующем: для «рома», подстроки подстроки «um», за которыми следуют «r», «ru» и «rum». Для «um» подстроки являются подстроками «m», за которыми следуют «u» и «um». Для «m» подстроки являются подстроками «», за которыми следует «m». Для "" подстроки просто "". Итак, окончательный список - «», «m», «u», «um», «r», «ru», «rum».

Хотя это не C++, вы должны иметь возможность перевести код на C++. Но это не обязательно то, что вы хотите, поскольку «rumm» имеет две «m» подстроки. Если вы считаете, что «rumm» должен иметь только одну «m» подстроку, оставьте комментарий, и я отправлю еще один ответ.

Answer 3

Во-первых, вы должны обратить внимание на отступ кода. Тогда, я не смотрю свой код, я написал код, чтобы достичь своей цели, следующим образом:

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