はじめに

---

string sが与えられ、その中に存在する長さ最大の回文を見つける問題．

コード全体

---

string longestPalindrome(string s) {
  int subLeft = 0;
  int subRight = 0;
  int subSize = 0;
  auto update = [&](int left, int right){
    int nowSize = right - left + 1;
    if( subSize < nowSize ){
      subLeft = left;
      subRight = right;
      subSize = nowSize;
    }
  };
  for(size_t center=0; center<s.length(); ++center){
    if(s[center] != s[center+1]) continue;
    size_t left = center;
    size_t right = center + 1;
    while( left!=0 && right!=s.length()-1 ){
      if( s[left-1] != s[right+1] ) break;
      left--;
      right++;
    }
    update(left, right);
  }
  for(size_t center=0; center<s.length(); ++center){
    size_t left = center;
    size_t right = center;
    while( left!=0 && right!=s.length()-1 ){
      if( s[left-1] != s[right+1] ) break;
      left--;
      right++;
    }
    update(left, right);
  }
  return s.substr(subLeft, subSize);
}

解説

---

subLeftは部分文字列の左端を、subRightは右端を、subSizeはその文字数を指す。 これらの変数を更新することで、最大長となる部分文字列を求める。

string longestPalindrome(string s) {
  int subLeft = 0;
  int subRight = 0;
  int subSize = 0;

update()は、上述した三つの変数を更新するラムダ式。 引数のleftとrightから、長さが現在の値より長い場合は更新する。

  auto update = [&](int left, int right){
    int nowSize = right - left + 1;
    if( subSize < nowSize ){
      subLeft = left;
      subRight = right;
      subSize = nowSize;
    }
  };

sの各要素に対し、要素を中心に回文を維持する限り左右に範囲を広げてそのleft・rightを引数としてupdate()する。 まずは部分文字列が偶数長の場合を行う。

  for(size_t center=0; center<s.length(); ++center){
    if(s[center] != s[center+1]) continue;
    size_t left = center;
    size_t right = center + 1;
    while( left!=0 && right!=s.length()-1 ){
      if( s[left-1] != s[right+1] ) break;
      left--;
      right++;
    }
    update(left, right);
  }

部分文字列が奇数長の場合も同様に行う。

  for(size_t center=0; center<s.length(); ++center){
    size_t left = center;
    size_t right = center;
    while( left!=0 && right!=s.length()-1 ){
      if( s[left-1] != s[right+1] ) break;
      left--;
      right++;
    }
    update(left, right);
  }

最大長の回文を返す。

  return s.substr(subLeft, subSize);
}