#5最長回文子列(中等)

タイトル
文字列sを指定すると、sの中で最も長い回文サブ列が見つかります.sの最大長さは1000と仮定できます.

   1：
  : "babad"
  : "bab"
  : "aba"         。

   2：
  : "cbbd"
  : "bb"

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/longest-palindromic-substring著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
コード#コード#

中心拡張法、時間複雑度:O(n^2)

#include
#include
//#include
#include
using namespace std;
class Solution {
public:
   string longestPalindrome(string s) {
   	int start = 0;
   	int end = 0;
   	for (int i = 0; i < s.size(); i++) {
   		int len1 = forLen(s, i, i);
   		int len2 = forLen(s, i, i + 1);
   		int len = max(len1, len2);
   		if (len > end - start + 1) {    //      1，                 
   			start = i - (len - 1) / 2;
   			end = i + len / 2;
   		}
   	}
   	return s.substr(start, end - start + 1);		// 1        ， 2    
   }

   int forLen(string& s, int left, int right) {
   	int L = left;
   	int R = right;
   	while (L >= 0 && R < s.size() && s[L] == s[R]) {
   		L--;
   		R++;
   	}
   	return (R - L - 1);     //    L R       ，     1
   }
};

Manacherアルゴリズム、時間の複雑さ:O(n)更新される.の