为什么字符串::resize和字符串::substr O(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::substr不是线性的,那么比较这两个字符串 T

如果这是真的,那么解决方案的时间复杂性不是 最小O(S.length()*T.length()),而不是O(S.length())(根据 解决方案)?感谢您的帮助!

此处的理由(根据您的链接)为:

哈希匹配以确保字符串确实匹配。既然他们这么做了 我们将删除。

那么“摊销”这部分意味着什么呢?因为你是对的,字符串比较在T中是线性的,如果算法对S的每个元素进行比较,那么时间复杂度将是O(TS)。

我思考摊销的最好方法是问这样一个问题:“我们接触每个元素多少次?”

一、 当T在字符串S上滑动时,T的每个元素一次。然后可能还会删除

但事实并非如此。因为我们只在有散列匹配的情况下进行比较,而且因为他们声称虚假匹配非常罕见,所以我们可以有效地 只有 当存在实际匹配时获取哈希匹配(该声明可能为真,也可能为假,这将需要对哈希算法进行调查),然后逻辑更改:

如果我们只在有匹配的情况下进行字符串比较,那么就在删除字符之前,我们比较了多少次元素 一、 ?

现在触摸一次进行比较,然后立即删除-然后它就消失了,再也没有触摸过。这使得每个元素的时间恒定O(2)=O(1),因此仅在元素数量上呈线性,总时间复杂度=O(S)。