從給定的字符串中查找給定長度的子序列？

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