C++에서 string :: substr()의 런타임은 무엇입니까?

Question

가능한 중복 :
What is the complexity of std::string::substr member function?

나는 일반 문자열 문제에 대한 순진 솔루션을 시도하고있다. 첫 번째 문자열의 모든 부분 문자열을 찾아 해시 집합에 추가하여이 작업을 수행합니다. 그런 다음 두 번째 문자열의 하위 문자열을 찾아서 해시 집합에 있는지 확인하고 길이가 현재 최대 하위 문자열보다 큰 경우 가장 긴 하위 문자열을 조정합니다. 내가 궁금해 한 것은 : str1의 길이 측면에서 substr의 런타임은 무엇입니까 (str1 길이가 이라고 가정 해 봅시다).

#include<hash_set> 

string longestCommonSubstring(string str1, string str2) { 
    hash_set<string> substrings; 
    string maxSubstring = ""; 
    int maxLength = 0; 

    for (int i = 0; i < str1.size(); i++) { 
     for (int j = i+1; j < str1.size(); j++) { 
      substrings.insert(str1.substr(i,j-i)); 
     } 
    } 

    for (int i = 0; i < str2.size(); i++) { 
     for (int j = i+1; j < str2.size(); j++) { 
      if (substrings.find(str2.substr(i,j-i)) != substrings.end()) { 
       if (j-i > maxLength) { 
        maxSubstring = str2.substr(i,j-1); 
        maxLength = j - i; 
       } 
      } 
     } 
    } 
} 

Answer 1

substr에 대해 지정된 복잡성이 없다

하지만 string는 일정 시간의 랜덤 액세스를 가지고 있으며, 그것을 복사 본질적으로 비용이 될 것이다, 그래서 substr은, 주어진 길이의 새 문자열을 만드는 많은 문자 .

GCC는 참조 카운트 (불법적으로)를 사용하여 std::string을 구현하므로 실제 복사 비용은 구현에 따라 다를 수 있습니다.

Answer 2

편집 : 죄송합니다. 질문을 잘못 이해했습니다. (질문을 제대로 읽지 못했습니다.)

시간 복잡도는 하드웨어에 따라 다르지만 요청 된 부분 문자열의 길이에 비례한다고 가정하는 것이 합리적입니다.

함수의 기능은 원래 문자열의 일부 복사본을 만드는 것입니다.