1

可能重复：
std::string::substr 成员函数的复杂性是多少？

我正在尝试对常见的子字符串问题进行天真的解决方案。为此，我首先找到第一个字符串的所有子字符串并将它们添加到哈希集中。然后，我找到第二个字符串的子字符串，看看它们是否存在于哈希集中，如果长度大于当前最大子字符串，则调整最长的子字符串。我想知道的是：就str1（假设str1有长度n）的长度而言，substr 的运行时间是多少？

#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 回答