c++ - 为什么 string::resize 和 string::substr O(1)

Question

我正在解决一个编码问题，其中我必须删除字符串 S 中所有出现的子字符串 T (请记住，删除 S 中出现的一次 T 可能会生成一个新的 T 出现)，然后返回所有删除后的结果字符串 S。 S和T的大小都可以达到10^6。

例如，如果我有 S = "aabcbcd"且 T = "abc"，则删除 S 中所有出现的 abc 会得到 S = "d"。

此问题的示例解决方案涉及从 S 一次一个字符构建字符串 R，每当 R 的结尾与 T 匹配时，我们将其从 R 中删除(R 结尾与 T 之间的比较由字符串决定)哈希)。

解决方案表明

Since this deletion is at the end of R this is just a simple O(1) resize operation.

但是，根据https://m.cplusplus.com/reference/string/string/resize/ string::resize 的时间复杂度与新字符串长度呈线性关系。 Ben Voigt 在 Why is string::resize linear in complexity? 中证实了这一点.

此外，在解决方案中，代码涉及使用 string::substr 来双重检查 R 的结尾和 T 是否匹配(因为 hash(R 的结尾)==hash(T) 不能保证 R 的结尾等于至 T):

/* If the end of R and T match truncate the end of R (and associated hash arrays). */
  if (hsh == thsh && R.substr(R.size() - T.size()) == T) {
    //...
  }

再一次，https://m.cplusplus.com/reference/string/string/substr/表示 string::substr 具有线性时间复杂度。

即使 string::substr 不是线性的，直接比较两个字符串仍然会导致比较结果在 T 的大小上是线性的。

如果这是真的，那么解决方案的时间复杂度不是至少是 O(S.length()*T.length())，而不是 O(S.length()) (根据解决方案)？如有任何帮助，我们将不胜感激!

Answer 1

string::resize 并不总是线性的。如果您要扩展字符串，则它与复制的字符数成线性关系，这可能是结果字符串中的总数(但如果字符串已经有足够的空间容纳您添加的字符，则可能会更少，所以它只需要写入新字符)。

使用resize来减小字符串的大小通常需要恒定的时间。在简化的形式中(并且省略了很多其他“东西”)string 可以看起来像这样:

template <class T>
class string {
     char *data;
     size_t allocated_size;
     size_t in_use_size;
public:
    void resize(size_t new_size) { 
        if (new_size < in_use_size) {
            in_use_size = new_size;
            data[in_use_size] = '\0';
        } else {
            // code to expand string to desired size in O(n) time
        }
    }
    // ...
};

因此，虽然在扩展字符串时它是线性的，但在减小大小时它通常具有恒定的复杂性。

至于使用substr，是的，在哈希匹配的情况下，substr本身将是线性的(它创建一个新的字符串对象)，您将进行线性复杂度比较。我猜他们只是假设哈希冲突非常罕见，可以忽略，因此对于大多数实际目的，这只在您进行实际匹配时才会发生。