Subcadena palindrómica más larga

Dada una cadena S, encuentre la subcadena palindrómica más larga en S. Puede suponer que la longitud máxima de S es 1000, y existe una subcadena palindrómica única más larga.

这道题 来源于leetcode, 有 很 多种 方法 可以 解决 , 最 直接 的Brute Force时间 复杂 度 是O (n ^ 3)的 ,Programación dinámica时间 复杂 度 是O (n ^ 2), 但 空间 复杂 度 也是O (n ^ 2)的 , 这儿 给出 一种Tiempo: O (n ^ 2)Espacio: O (1)的 方法。

关键 点 : 回文 字符串 是 中心 对称 的

从 中心 开始 向 两侧 扩展 , 代码 如下 :

class Solution {
public:
string longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s.empty())
return s;
int maxl=0,maxr=0,size=1;
for(int i=0;i<s.length();i++)
{
int l=i-1,r=i+1,il=i,ir=i+1;
while(l>=0 && r<s.length() && s[l]==s[r])
l
--,r++;
while(il>=0 && ir<s.length() && s[il]==s[ir])
il
--,ir++;
if(r-l<ir-il)
l
=il,r=ir;
if(r-l-1>size)
maxl
=l+1,maxr=r-1,size=r-l-1;
}
return s.substr(maxl,size);
}
};

该 问题 还有 一种Tiempo: O (n)Espacio: O (n)的 算法 ,Algoritmo de Manacher