客所以会有一种冲动设立g[i]表示以第i位为结尾的最长回文子串长度然后再遍历一遍取最大长度即可。

但是后来发现如果g[i]如此表示很难得到递推公式。

所以转到二维设立g[i][j]bool将其表示以第i位开头第j位结尾的子串是否是回文子串并用l和r记录到目前为止最长回文子串的左索引和右索引。

所以递推公式为g[i][j]{如果s[i]s[j]且g[i1][j-1]是回文子串则为1}。

此时有需要独立判断两种情况第一种情况是子串长度为1g[i][i]1第二种情况是子串长度为2(j-i1)如果s[i]s[j]则g[i][j]2。

还要说明一点为什么在二重循环时i

的顺序是从i到len。

因为由g[i1][j-1]推及g[i][j]所以我们需要先从左下角向右上角开始推行数(i)从大到小列数(j)从小到大。

class

g(len,vectorbool(len,false));for(int

l0;int

ji;jlen;j){if(s[i]s[j]){if(j-i1){g[i][j]true;}else{if(i1len

j-10

g[i1][j-1]true){g[i][j]true;}}}if(g[i][j]true

s.substr(l,r-l1);}

range(len_s):g[i][i]Truel0r0for

range(i,len_s):if