为什么 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 之间的比较由字符串哈希确定）。

解决方案说

由于此删除位于 R 的末尾，因此这只是一个简单的 O(1) 调整大小操作。

但是，根据https://m.cplusplus.com/reference/string/string/resize/， string::resize 的时间复杂度与新字符串长度呈线性关系。Ben Voigt 在《为什么 string::resize 的复杂度是线性的？》中证实了这一点。。

另外，在解决方案中，代码涉及使用 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它本身将是线性的（它创建一个新string对象），并且您将进行线性复杂度比较。我猜他们只是假设哈希冲突很少见，可以忽略，所以对于大多数实际目的，这种情况只有在实际匹配时才会发生。