1

重複の可能性:
std::string::substr メンバー関数の複雑さは?

一般的な部分文字列の問題に対する素朴な解決策を試みています。これを行うには、まず最初の文字列のすべての部分文字列を見つけて、それらをハッシュ セットに追加します。次に、2 番目の文字列の部分文字列を見つけて、それらがハッシュ セットに存在するかどうかを確認し、長さが現在の最大部分文字列よりも大きい場合は、最長の部分文字列を調整します。私が疑問に思っていたのは、substrの長さに関して、substrの実行時間は何ですかstr1（たとえば、str1has length n）？

#include<hash_set>

string longestCommonSubstring(string str1, string str2) {
    hash_set<string> substrings;
    string maxSubstring = "";
    int maxLength = 0;

    for (int i = 0; i < str1.size(); i++) {
        for (int j = i+1; j < str1.size(); j++) {
            substrings.insert(str1.substr(i,j-i));
        }
    }

    for (int i = 0; i < str2.size(); i++) {
        for (int j = i+1; j < str2.size(); j++) {
            if (substrings.find(str2.substr(i,j-i)) != substrings.end()) {
                if (j-i > maxLength) {
                    maxSubstring = str2.substr(i,j-1);
                    maxLength = j - i;
                }
            }
        }
    }
}
4

2 に答える 2

2

には指定された複雑さはありませんが、substr一定string時間のランダムアクセスがあり、指定されsubstrた長さの新しい文字列を作成するため、本質的にその多くの文字をコピーするコストになります。

GCCstd::stringは参照カウントを実装しているため (違法です)、コピーを作成する実際のコストは実装によって異なる場合があることに注意してください。

于 2012-10-05T02:23:12.383 に答える
-1

編集：申し訳ありませんが、質問を誤解しました（質問を正しく読んでいませんでした）。

時間の計算量はハードウェアに依存しますが、要求された部分文字列の長さに比例すると考えるのが妥当です。

関数が行うことは、元の文字列の一部のコピーを作成することです。

于 2012-10-05T02:23:13.340 に答える