回文字串的数量

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解题思路:
主要思路，我们使用中心扩散的思想，从反转中心向两边扩散，记录所有的回文子串的数量
其中有一些细节我们要注意：回文字串的长度分为奇偶，如果为奇数，中间的数就是回文中心，如果是偶数，我们令两个数均为对称中心，我们使用一个函数来统一实现

public int countSubstrings(String s) {
        int ans = 0;
        for(int i  = 0;i<s.length();i++){
            ans+=isReverse(s,i,i);
            ans+=isReverse(s,i,i+1);
        }
        return ans;
    }
public int isReverse(String s,int i,int j){
    int count = 0;
    while(i>=0&&j<=s.length()-1&&String.charAt(i)==String.charAt(j)){
        count++;
        i--;
        j++;
    }
    return count;
}

拓展：上述方法，主函数中遍历一遍s，调用函数中再次遍历s，复杂度o（n^2），所以我们可以使用解决最长回文字串的经典方法，马拉车算法，将时间复杂度降为o(n)，下面我们来分析以下马拉车算法: