从给定的字符串中查找给定长度的子序列？

Question

要找到给定长度的字符串我有一个递归代码（如下图所示）的子序列，但它需要太多的时间，当字符串长度大....

void F(int index, int length, string str) 
{ 
    if (length == 0) { 
cout<<str<<endl; 
//int l2=str.length(); 
//sum=0; 
    //for(int j=0;j<l2;j++) 
//sum+=(str[j]-48); 
//if(sum%9==0 && sum!=0) 
    //{c++;} 
//sum=0; 
    } else { 
    for (int i = index; i < n; i++) { 
     string temp = str; 
     temp += S[i]; 
    //sum+=(temp[i]-48); 
     F(i + 1, length - 1, temp); 
    } 
    } 
} 

请帮我一些实现非递归代码或其他东西的想法。

Answer 1

你提到你当前的代码太慢，当输入字符串长度很大。如果你可以提供一个具体的例子以及你的时间信息，那么我们会知道你认为“太慢”了。您还应该指定您认为可以接受的运行时间。这里有一个例子：

我将从一个初始版本开始，我认为它与您当前的算法类似。它生成> = 2长度的所有子序列：

#include <iostream> 
#include <string> 

void subsequences(const std::string& prefix, const std::string& suffix) 
{ 
    if (prefix.length() >= 2) 
     std::cout << prefix << std::endl; 

    for (size_t i=0; i < suffix.length(); ++i) 
     subsequences(prefix + suffix[i], suffix.substr(i + 1)); 
} 

int main(int argc, char* argv[]) 
{ 
    subsequences("", "ABCD"); 
} 

运行该程序产生以下输出：

AB 
ABC 
ABCD 
ABD 
AC 
ACD 
AD 
BC 
BCD 
BD 
CD 

现在，让我们将输入字符串更改为更长的时间。我将使用26个字符的输入字符串：

"ABCDEFGHIJKLMNOPQRSTUVWXYZ" 

这会生成67,108,837个子序列。我不会在这里列出他们:-)。在我的机器上，上面显示的代码用26个字符的输入字符串运行只需78秒以上（不包括输出到cout）。

当我寻找优化上述代码的方法时，跳出的一件事就是它为子序列（）的每次递归调用创建两个新的字符串对象。如果我们可以预先分配一次空间然后传递指针呢？版本2：

#include <stdio.h> 
#include <malloc.h> 
#include <string.h> 

void subsequences(char* prefix, int prefixLength, const char* suffix) 
{ 
    if (prefixLength >= 2) 
     printf("%s\n", prefix); 

    for (size_t i=0; i < strlen(suffix); ++i) { 
     prefix[prefixLength] = suffix[i]; 
     prefix[prefixLength + 1] = '\0'; 
     subsequences(prefix, prefixLength + 1, suffix + i + 1); 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    const char *inputString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    char *prefix = (char*) _malloca(strlen(inputString) + 1); 

    subsequences(prefix, 0, inputString); 
} 

这产生相同的67108837子序列，但执行时间是现在刚刚超过2秒（再次，通过printf的不含输出）。

Answer 2

您的代码可能很慢，因为您的字符串很大。对于n个独特元素的序列，存在长度为k的（n个k个）子序列。这意味着对于“ABCDEFGHIJKLMNOPQRSTUVWXYZ”这个序列，有长度为13的10.400.600个不同的子序列。这个数字增长得相当快。

不过，既然你问，这里是一个非递归函数，它需要一个字符串STR和大小ñ并打印长度该字符串的n个的所有序列。

void print_subsequences(const std::string& str, size_t n) 
{ 
    if (n < 1 || str.size() < n) 
    { 
     return; // there are no subsequences of the given size 
    } 
    // start with the first n characters (indexes 0..n-1) 
    std::vector<size_t> indexes(n); 
    for (size_t i = 0; i < n; ++i) 
    { 
     indexes[i] = i; 
    } 
    while (true) 
    { 
     // build subsequence from indexes 
     std::string subsequence(n, ' '); 
     for (size_t i = 0; i < n; ++i) 
     { 
      subsequence[i] = str[indexes[i]]; 
     } 
     // there you are 
     std::cout << subsequence << std::endl; 
     // the last subsequence starts with n-th last character 
     if (indexes[0] >= str.size() - n) 
     { 
      break; 
     } 
     // find rightmost incrementable index 
     size_t i = n; 
     while (i-- > 0) 
     { 
      if (indexes[i] < str.size() - n + i) 
      { 
       break; 
      } 
     } 
     // increment that index and set all following indexes 
     size_t value = indexes[i]; 
     for (; i < n; ++i) 
     { 
      indexes[i] = ++value; 
     } 
    } 
}