最长回文子串与最长回文子序列的爱恨情仇
给定一个字符串，请你求出其中的最长回文子串的长度。
例如，给定字符串 Is PAT&TAP symmetric?，最长回文子串为 s PAT&TAP s，其长度是 1111。
输入格式
包含一个非空字符串。
输出格式
输出一个整数，表示给定字符串的最长回文子串的长度。
数据范围
给定字符串的长度不超过 1000。
输入样例：
Is PAT&TAP symmetric?
输出样例：
11
好吧，这道题目实属非常经典的一道例题，有很多种做法，下面开始介绍两种方法。
(小声bb，其实还有一种马拉车算法，之后有时间再讲，其实不是很重点的一种方法，也比较简单)
在介绍这三种方法之后，我们需要对比一下，leetcode上面的一道题目
516. 最长回文子序列 - 力扣（LeetCode） (leetcode-cn.com)
仔细想一下，子序列与子串的difference在什么地方。在dp做法的时候，在状态表示，状态转移的过程中有什么明显的区别？？？
一、线性dp
状态表示：f[i] [j] 表示什么呢？因为其实线性dp不是我第一次做出来这个题目所用的方法。
我闪过几个角度，like 从i到j这一段中最长的子串的长度？ 其实有点像后面要说的，子序列的表示。
或者是f[i] [j] 表示i到j是回文子串同时储存着长度？有点脱裤子放… 不对，就像是为了dp而dp的感觉….
最终选择dp[i] [j] 不仅表示回文子串而且存贮这长度这种表示方式，没什么原因，就是感觉思路简单，便于比较。
状态属性：max
base case：每一个字符都可以表示为长度为一的回文子串。
状态转移：这样想，所有回文子串(注意连续)，都是只可能有一种状态转移来的，dp[i+1] [j-1] +2 转移来的，so 只需要一种语句即可。
直接
if(a[i] == a[j])
{
f[i][j] = f[i+1][j-1] + 2 ;
}
else
{
f[i][j] = -1000 ;
}
两个雷区
一是遍历顺序，这个注意即可，细心就行。
二是对不满足条件的处理，我之前就是因为，没有上述的else的语句，被卡了大概5分钟…..
我们这样想，因为f表示的是连续符合要求的子串，如果不满足a[i] == a[j]，其实就是等于把这个i到j给pass了，给他一个大的负数就是等于，不让他影响后续res的max函数的判断，这样会省下很多烦恼。
代码如下：
#include
using namespace std ;
const int N = 1010 ;
string a ;
int f[N][N] ;
int main()
{
getline(cin , a) ;
int n = a.size() ;
if(n == 1)
{
cout << 1 << endl ;
}
else
{
int res = 1 ;
for(int i = 0 ; i < n ; ++ i)
{
f[i][i] = 1 ;
}
for(int i = n-1 ; i >= 0 ; --i)
{
for(int j = i + 1 ; j < n ; j ++)
{
if(a[i] == a[j])
{
f[i][j] = f[i+1][j-1] + 2 ;
}
else
{
f[i][j] = -10000 ;
}
res = max(res , f[i][j]) ;
}
}
cout << res << endl ;
}
return 0 ;
}
二、中心扩散法
这一种方法其实是我第一次做出来的方法，我觉得他比较符合一般思维的特点。具体逻辑是先进行一次循环遍历，将自己所指向的下标作为回文子串的中心。向左右开始扩散，判断方法是字符是否相同，如果字符相同，即为之前的数量加上2即可。再用一个res储存最大值就可以。
但是，最主要注意的是需要分成奇数回文字符串与偶数回文字符串，分别循环，最后取大值即可。
OK。Talk is cheap, show me your code
贴个代码：
#include
using namespace std ;
const int N = 1010 ;
int f[N][N] ;
string a ;
int main()
{
getline(cin , a) ;
int n = a.size() ;
if(n == 1) cout << 1 << endl ;
else
{
int res = -1000 ;
for(int i = 0 ; i < n ; ++ i)
f[i][i] = 1 ;
for(int i = 0 ; i < n ;++ i) //奇数回文
{
int l = i - 1 ; int r = i + 1 ;
while(l >= 0 && r < n && a[l] == a[r])
{
f[l][r] = f[l+1][r-1] + 2 ;
l -- ; r ++ ;
}
res = max(res ,f[l+1][r-1] ) ;
}
for(int i = 0 ; i < n ; ++ i) //偶数回文
{
int l = i ; int r = i + 1 ;
while(l >= 0 && r < n && a[l] == a[r])
{
f[l][r] = f[l+1][r-1] + 2 ;
l -- ; r ++ ;
}
res = max(res ,f[l+1][r-1] ) ;
}
cout << res << endl ;
}
return 0 ;
}
———-10-12 添加———————————————————————————————————————————————————
ok，在看manacher算法的时候，他的预处理也可以用在中心扩散法(暴力)。因为暴力解法需要分两种情况，一种是偶数的，还有一种是奇数的。可以在string a的每一个字符左右两面都添加一个额外符号，相同即可。所以原数据范围由n到2*n+1 ;
一定可以转化为奇数来做。
但是注意两个细节：
一、申请的范围N, 因为数据由1000到了2001，所以申请超过2010就可以了。
二、最后的输出结果，由于c++除法自动向下取整，所以结果就是res >> 1即可。别的没有什么。
所以，贴个代码：
#include
using namespace std ;
const int N = 2010 ;
string a ;
int f[N][N] ;
int main()
{
getline(cin , a) ;
string b = "" ;
int n = a.size() ;
for(int i = 0 ; i < n ; ++ i)
{
b.push_back('#') ;
b.push_back(a[i]) ;
}
b.push_back('#') ;
n = b.size() ;
for(int i = 0 ; i < n ; ++ i)
{
f[i][i] = 1 ;
}
int res = 1 ;
for(int i = 1; i < n ; ++ i)
{
int l = i -1 ;
int r = i + 1 ;
while(l >= 0 && r < n && b[l] == b[r])
{
f[l][r] = f[l+1][r-1] + 2 ;
l -- ; r++ ;
}
res = max(res , f[l+1][r-1]) ;
}
int ans = res / 2 ;
cout << ans << endl ;
return 0 ;
}
ok.以上就是最长回文子串的做法，我们来看最长回文子序列的题目。
516. 最长回文子序列 - 力扣（LeetCode） (leetcode-cn.com)
这就是典型的线性dp可以做出来的题，我们按照经典模板走一下。
状态表示：dp[i] [j] 表示在下标为i到j的一段字符串中， 最长子序列的长度。
状态属性：max
base case：每一个字符都可以看成是一个长度为一的回文字符串。
状态转移：字符串经典分割，按照遍历时候，字符是否相同进行分割。
如果相同，f[i] [j] = f[i+1] [j-1] + 2 ;
如果不同 ， f[i] [j] = max(f[i] [j-1] , f[i+1] [j]) ;
感觉都成了肌肉记忆了…………
贴个代码：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size() ;
if(n == 1) return 1 ;
vector> f(n , vector (n, 0)) ;
for(int i = 0 ; i < n ; ++ i)
{
f[i][i] = 1 ;
}
for(int i = n-1 ; i >= 0 ; --i)
{
for(int j = i + 1 ; j < n ; ++ j) //一个小细节，注意遍历的顺序，这是根据状态转移的式子来的。
{
if(s[i] == s[j])
{
f[i][j] = f[i+1][j-1] + 2 ;
}
else
{
f[i][j] = max(f[i][j-1] , f[i+1][j]) ;
}
}
}
return f[0][n-1] ;
}
};
可以明显的感觉到两者之间的方法的差异。
本质上，其实就是定义的差别，即连续与不连续的区别。这就导致了在dp的时候，状态表示的差异。
子串
状态表示：是饱满的，就是相当于中间不能有任何空隙，任何使得中间有空隙的f段都会被直接pass。
状态属性：max
base case：不说了
状态转移：唯一一种形成的方式，就是相等才会前进，如果不等，就直接pass
子序列
状态表示：相等于很宽容，里面既可以有合乎要求的，也可以有方案外的。
状态属性：同子串
base case：同子串
状态转移：经典按照字符串==方式进行划分， if 就+2 else 就回退。
好了，终于写完了！！！
之后有时间介绍一下，马拉车算法。
