returns 一个字符串的所有子串的递归函数

Question

我需要用C++实现一个函数，

vector<string> generateSubstrings(string s),

那 return 是一个字符串的所有子串的向量。例如，字符串“rum”的子串是七个字符串

“r”、“ru”、“朗姆酒”、“u”、“um”、“m”、“”。

该函数必须是递归的，并且必须 return 将结果作为向量。

到目前为止，这是我的代码。它只打印 "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

这是使用 Python 的答案。它为 "rum" 打印了正确的结果，但是对于 "rumm" 它打印了两个 "m" 子串，原因很明显：

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

算法的思路是这样的：对于"rum"，子串是"um"后面跟着"r"、"ru"和[=17=的子串].对于 "um"，子字符串是 "m" 后跟 "u" 和 "um" 的子字符串。对于 "m"，子字符串是“”后跟 "m" 的子字符串。对于“”，子字符串只是“”。所以，最后的列表是 "", "m", "u", "um", "r", "ru", "rum".

虽然这不是 C++，但您应该能够将代码转换为 C++。但这不一定是您想要的，因为 "rumm" 有两个 "m" 子字符串。如果您认为 "rumm" 应该只有一个 "m" 子字符串，请发表评论，我会 post 另一个答案。

Answer 2

在你的作业中写着递归函数必须像

这样声明

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

returns 一个字符串的所有子串的递归函数

Recursive Function that returns all substrings of a string

c++

string

recursion

substring

vector