1

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

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

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

4

2 回答 2

2

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

我将从一个我认为与您当前算法相似的初始版本开始。它生成所有长度 >= 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 个字符的输入字符串运行（不包括输出到 cout）只需要 78 秒多一点。

当我寻找优化上述代码的方法时，跳出来的一件事是它为每个对 subsequences() 的递归调用创建了两个新的字符串对象。如果我们可以预先分配空间然后简单地传递指针会怎样？版本 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);
}

这会生成相同的 67,108,837 个子序列，但现在执行时间刚刚超过 2 秒（同样，不包括通过 printf 的输出）。

于 2012-08-04T04:54:46.997 回答
0

您的代码可能很慢，因为您的字符串很大。对于具有 n 个唯一元素的序列，有 (n over k) 个长度为 k 的子序列。这意味着对于序列“ABCDEFGHIJKLMNOPQRSTUVWXYZ”，有 10.400.600 个长度为 13 的不同子序列。这个数字增长得非常快。

然而，既然你问了，这里有一个非递归函数，它接受一个字符串str和一个大小n并打印该字符串的所有长度为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;
        }
    }
}
于 2015-04-30T05:31:28.443 回答