どちらも最長のパリンドローム部分文字列を検索するためにExpand Around Centerアルゴリズムを使用していますが、なぜ高速化されていますか？

Question

leetcodeで6msしか実行できない高速なソリューションAがあります。これはManacher Algorithm（leetcodeでは6ms）とほぼ同じ速度です。

class Solution { 
public: 
    string longestPalindrome(string s) { 
     if (s.empty()) return ""; 
     if (s.size() == 1) return s; 
     int min_start = 0, max_len = 1; 
     for (int i = 0; i < s.size();) { 
      if (s.size() - i <= max_len/2) break; 
      int j = i, k = i; 
      while (k < s.size()-1 && s[k+1] == s[k]) ++k; // Skip duplicate characters. 
      i = k+1; 
      while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; } // Expand. 
      int new_len = k - j + 1; 
      if (new_len > max_len) { min_start = j; max_len = new_len; } 
     } 
     return s.substr(min_start, max_len); 
    } 
}; 

そして、なぜ吹き出し溶液Bが溶液Aと比較して遅いのか分かりませんが、これは16msの実行時間がかかります。彼らは両方ともセンターアルゴリズムの周りに展開し、Oを取得しているので

class Solution { 
public: 
    int expandAroundCenter(string s, int left,int right) { 
     int L = left, R = right; 
     while(L >=0 && R < s.length() && s[L] == s[R]) { 
      L--; 
      R++; 
     } 

     return R - L - 1; 
    } 

    string longestPalindrome(string s) { 
     int start = 0, end = 0; 
     if (s.empty()) return ""; 
     if (s.size() == 1) return s; 
     for(size_t i = 0; i < s.length(); i++) { 
      int len1 = expandAroundCenter(s, i, i); 
      int len2 = expandAroundCenter(s, i, i + 1); 
      int len = std::max(len1, len2); 
      if(len > end - start + 1) { 
       start = i - (len - 1)/2; 
       end = i + len/2; 
      } 

      if(start + len > s.length()) break; 
     } 

     return s.substr(start, end - start + 1); 
    } 

}; 

（Nは^ 2）時間の複雑さとO（1）スペースの複雑さは、私が唯一のコーディングを推測することができます（ManacherのアルゴリズムはO（n）の時間計算量を取得します）メソッドが最も重要な要素です。まあ、それが事実なら、私は本当に理由を知りたい。 optimazationで

、溶液Bは、依然として最も可能性の高いベンチマークの重要な部分を構成する最初の文字列を励起A.

class Solution { 
public: 
    int expandAroundCenter(const string& s, int left,int right) { 
     int L = left, R = right; 
     while(L >=0 && R < s.length() && s[L] == s[R]) { 
      L--; 
      R++; 
     } 

     return R - L - 1; 
    } 

    string longestPalindrome(const string& s) { 
     int max_len = 0; 
     int min_start = 0; 
     if (s.empty()) return ""; 
     if (s.size() == 1) return s; 
     for(size_t i = 0; i < s.length(); i++) { 
      if (s.size() - i <= max_len/2) 
       break; 

      int j = i, k = i; 
      while (k < s.size()-1 && s[k+1] == s[k]) ++k; 
      int len = expandAroundCenter(s, j, k); 

      if(len > max_len) { 
       max_len = len; 
       min_start = j - (len - (k - j + 1))/2; 
      } 
     } 

     return s.substr(min_start, max_len); 
    } 

}; 

Answer 1

アルゴリズムAスキップより50％遅いです。アルゴリズムBは、そのトラップのために落ち、ポンピングされたシーケンスを2回、述語の各呼び出しごとに1回反復する。

ベンチマークスイートを使用して、すべての単一文字の繰り返しを[Pad][Character][Pad]に置き換えると、この最適化は中断されます。