title: What is the runtime of string::substr() in C++?
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/12449298/what-is-the-complexity-of-stdstringsubstr-member-function">What is the complexity of std::string::substr member function?</a>  </p>
  </blockquote>
  
  
  
  <p>I am attempting a naive solution to the common substring problem.  I do this by first finding all the substrings of the first string and adding them to a hash set.  Then, I find the substrings of the second string and see if they exist in the hash set, and adjust the longest substring if the length is greater than the current max substring.  What I was wondering is: what is the runtime of substr, in terms of the length of the <code>str1</code> (let's say <code>str1</code> has length <code>n</code>)?</p>
  
  <pre><code>#include&lt;hash_set&gt;
  
  string longestCommonSubstring(string str1, string str2) {
      hash_set&lt;string&gt; substrings;
      string maxSubstring = "";
      int maxLength = 0;
  
      for (int i = 0; i &lt; str1.size(); i++) {
          for (int j = i+1; j &lt; str1.size(); j++) {
              substrings.insert(str1.substr(i,j-i));
          }
      }
  
      for (int i = 0; i &lt; str2.size(); i++) {
          for (int j = i+1; j &lt; str2.size(); j++) {
              if (substrings.find(str2.substr(i,j-i)) != substrings.end()) {
                  if (j-i &gt; maxLength) {
                      maxSubstring = str2.substr(i,j-1);
                      maxLength = j - i;
                  }
              }
          }
      }
  }
  </code></pre>