题目：（和【5】类似）（这个需要静下心来看吖~）
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
中心扩展法：
这是一个比较巧妙的方法，实质的思路和动态规划的思路类似。
比如对一个字符串 ababa，选择最中间的 a 作为中心点，往两边扩散，第一次扩散发现 left 指向的是 b，right 指向的也是 b，所以是回文串，继续扩散，同理 ababa 也是回文串。
这个是确定了一个中心点后的寻找的路径，然后我们只要寻找到所有的中心点，问题就解决了。
中心点一共有多少个呢？看起来像是和字符串长度相等，但你会发现，如果是这样，上面的例子永远也搜不到 abab，想象一下单个字符的哪个中心点扩展可以得到这个子串？似乎不可能。所以中心点不能只有单个字符构成，还要包括两个字符，比如上面这个子串 abab，就可以有中心点 ba 扩展一次得到，所以最终的中心点由 2 * len - 1 个，分别是 len 个单字符和 len - 1 个双字符。
如果上面看不太懂的话，还可以看看下面几个问题：
为什么有 2 * len - 1 个中心点？
aba 有5个中心点，分别是 a、b、c、ab、ba
abba 有7个中心点，分别是 a、b、b、a、ab、bb、ba
什么是中心点？
中心点即 left 指针和 right 指针初始化指向的地方，可能是一个也可能是两个
为什么不可能是三个或者更多？
因为 3 个可以由 1 个扩展一次得到，4 个可以由两个扩展一次得到
import java.util.*;
class Solution {
public int countSubstrings(String s) {
// 中心扩展法
int ans = 0;
for (int center = 0; center < 2 * s.length() - 1; center++) {
// left和right指针和中心点的关系是？
// 首先是left，有一个很明显的2倍关系的存在，其次是right，可能和left指向同一个（偶数时），也可能往后移动一个（奇数）
// 大致的关系出来了，可以选择带两个特殊例子进去看看是否满足。
int left = center / 2;
int right = left + center % 2;
//注意这里不能用s.charAt(left).equals(s.charAt(right))，因为char是基本数据类型，而equals比较的是引用数据类型
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
ans++;
left--;
right++;
return ans;
public class Main {
public static void main(String[] args) {
String temp = "ababa";
Solution p = new Solution();
int b = p.countSubstrings(temp);
System.out.println("输出结果"+ b);
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载
【问题1】求字符串回文子序列的个数问题：给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中，回文子序列为”a”, “a”, “aa”, “b”, “aba”，共5个。内容相同位置不同的子序列算不同的子序列。分析与解法：与子串不同，子序列是可以不连续的，只要元素的前后相对位置不变。解法一：递归假设s[0 … n-1]是给定的序列，长度为让 c(0,n-1)表
对于任意字符串，如果头尾字符不相等，则[如abc,为f(abc)=f(ab)+f(bc)-f(c )=2+2-1]:
字符串的回文子序列个数=去掉头的字符串的回文子序列个数+去掉尾的字符串的回文子序列个数-去掉头尾的字符串的回文子序列个数；
如果头尾字符相等，则[如aba,为f(aba)=f(ab)+f(ba)+1=2+2+1]:
字符串的回文子序列个数=去掉头的...
如果一个子序列从左向右和从右向左读都一样，则称之为回文。例如，序列ACGTGTCAAAATCG有很多回文子序列，比如ACGCA和AAAA。请给出一个算法，求出最长的回文子序列
int longestCommonSubsequence(string text1, string text2) {
//从底到上的动态规划
int n = text1.length(), m = text2.length();
if (0 == n*m)
return 0;
//dp[i][j]: text1[0...i-1]与tex
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?
输出样例：
Manacher算法可以用线性的时间复杂度解决上述问题，思想是基于对称解决问题。
首先，设置len数组用来保存每个位置最大回
void getAllSubstring(string s,vector<string> &res){
for (int i = 0; i < s.size(); i++){
for (int j = 1; j <= s.size()-i; j++){
res.emplace(s.substr(i, j));
一个可能的最长回文子序列为 “bb”。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-...
