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 文字の入力文字列を使用して上記のコードを実行するのに 78 秒強かかります (cout への出力を除く)。

上記のコードを最適化する方法を探していると、subsequences() の再帰呼び出しごとに 2 つの新しい文字列オブジェクトが作成されていることがわかります。事前にスペースを事前に割り当ててから、単にポインターを渡すことができたらどうでしょうか? バージョン 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 に答える