我正在解决一个编码问题，其中我必须删除字符串 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 …