目录
一、暴力法
二、动态规划
三、中心扩散法
四、Manacher 算法
求最长回文子串的方法：（子串一定是连续的，子序列不是）
LeetCode题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
枚举子串的起点和终点，O(n^2) ，再用O(n)的时间判断枚举的这个子串是不是回文的。
时间复杂度：O(n^3) 空间复杂度：O(1)
定义状态： p[ i ] [ j ] 表示字符串从 i 到 j 是否为回文串。
状态转移：已知 p[ i+1 ] [ j-1 ] == 1 是回文串，如果 s[i]==s[j] ，说明可以向外扩散一步，则 p[ i ] [ j ]==1
状态转移方程： if (p[i+1][j-1] && s[i]==s[j]) p[i][j]=1; else p[i][j]=0;
初始化：一个字符本身一定是回文的，p[i][i]=1， 因为状态转移涉及-1操作，所以需要预处理长度为2的回文串，即if (s[i]==s[i-1]) p[i-1][i]=1;
class Solution { public: string longestPalindrome(string s) { //预处理 bool p[1005][1005]={0}; p[0][0]=1; for (int i=1; i<s.size(); i++){ p[i][i]=1; if (s[i]==s[i-1]) p[i-1][i]=1; } //动态规划 for (int l=2; l<s.size(); l++){ for (int i=0; i<s.size()-l; i++){ int j=i+l; if (p[i+1][j-1] && s[i]==s[j]) p[i][j]=1; else p[i][j]=0; } } //统计答案 int ans=0; int t=0; for (int i=0; i<s.size(); i++){ for (int j=i; j<s.size(); j++){ if (p[i][j]==1 && j-i+1>ans){ ans=j-i+1; t=i; } } } string ss(s,t,ans); //提取答案 return ss; } };时间复杂度：O(n^2) 空间复杂度：O(n^2)
枚举每一个字符，把这个字符当做回文中心，然后O(n)时间复杂度向两边扩散。
需要注意的是奇偶中心的问题，我们可以把一个字符分别当做奇中心和偶中心看待，只是扩散和统计答案上略有不同，但是思想是一致的。
class Solution { public: string longestPalindrome(string s) { int ans=0,t; //ans答案长度，t回文起点 int sum,p,q; //扩散用的变量 for(int i=0; i<s.size(); i++){ //枚举每一个字符 sum=1; p=i-1; q=i+1; //奇中心 while (p>=0 && q<s.size() && s[p]==s[q]){ sum+=2; p--; q++; } if (sum>ans) ans=sum,t=i-ans/2; sum=0; p=i; q=i+1; //偶中心 while (p>=0 && q<s.size() && s[p]==s[q]){ sum+=2; p--; q++; } if (sum>ans) ans=sum,t=i-ans/2+1; } string ss(s,t,ans); return ss; } };时间复杂度：O(n^2) 空间复杂度：O(1)
中心扩散法的时间复杂度最坏是O(n^2)。例如字符串是"aaaaaaa"。 那假如回文串的答案长度很短，形如"abcdefgh"，那么意味着往两边扩散的时候，很早就会结束，速度会快很多。 所以综上我们可以得出，让中心扩散法变慢的主要原因是那些可以一直扩散的。 而马拉车算法正是为了解决这种扩散情况而发明的。
马拉车算法的思想是把动态规划和中心扩散两种方法结合起来，用空间换取时间。 当第i个字符进行扩散时，先查看是否能借取之前的扩散数组p，再用中心扩散。
Manacher 算法【马拉车算法详解】最长回文子串
时间复杂度：O(n) 空间复杂度：O(n)
