title: Why is string::resize and string::substr O(1)
body: <p>I am working on a coding problem in which I have to delete all occurrences of a substring T in a string S (keeping in mind that removing one occurrence of T in S may generate a new occurrence of T), and then to return the resulting string S after all deletions. The size of both S and T can be up to 10^6.</p>
  <p>For example, if I have S = &quot;aabcbcd&quot; and T = &quot;abc&quot;, then removing all occurrences of abc in S results in S = &quot;d&quot;.</p>
  <p>The sample solution to this problem involves building a string R from S one character at a time, and whenever the end of R matches T, we delete  it from R (the comparison between the end of R and T is determined by string hashing).</p>
  <p>The solution says that</p>
  <blockquote>
  <p>Since this deletion is at the end of R this is just a simple O(1) resize operation.</p>
  </blockquote>
  <p>However, according to <a href="https://m.cplusplus.com/reference/string/string/resize/" rel="nofollow noreferrer">https://m.cplusplus.com/reference/string/string/resize/</a> the time complexity of string::resize is linear in the new string length. Ben Voigt confirms this in <a href="https://stackoverflow.com/questions/29319712/why-is-stringresize-linear-in-complexity">Why is string::resize linear in complexity?</a>.</p>
  <p>Also, in the solution the code involves using string::substr to double check if the end of R and T match (since hash(the end of R)==hash(T) does not guarantee the end of R equals to T):</p>
  <pre><code>/* If the end of R and T match truncate the end of R (and associated hash arrays). */
    if (hsh == thsh &amp;&amp; R.substr(R.size() - T.size()) == T) {
      //...
    }
  </code></pre>
  <p>Once again, <a href="https://m.cplusplus.com/reference/string/string/substr/" rel="nofollow noreferrer">https://m.cplusplus.com/reference/string/string/substr/</a> says that string::substr has linear time complexity.</p>
  <p>Even if string::substr wasn't linear, then comparing the two strings directly would still cause the comparison to be linear in the size of T.</p>
  <p>If this is true, wouldn't the time complexity of the solution be at least O(S.length()*T.length()), instead of O(S.length()) (according to the solution)? Any help is appreciated!</p>