Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
給定一字符串，統(tǒng)計其含有的回文子串的數(shù)量。

Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

• The input string length won't exceed 1000.

思路
【回文中心法】
定義當前掃描點i為掃描的回文中心，向兩端發(fā)散掃描并統(tǒng)計有效的回文串個數(shù)。
此種從中間到兩邊的掃描判定避免了將aaa、aba、區(qū)別對待的情形，但是要注意考慮回文串長度為奇數(shù)（aaa）和偶數(shù)（aaaa）的情況。
時間復雜度O(n^2)。

public class Solution {
    int count = 0;
   
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
       
        for (int i = 0; i < s.length(); i++) { // i is the mid point
            extendPalindrome(s, i, i); // odd length;
            extendPalindrome(s, i, i + 1); // even length
        }
       
        return count;
    }
   
    private void extendPalindrome(String s, int left, int right) {
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++; left--; right++;
        }
    }
}

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n=len(s)
        ans=0
        for center in xrange(2*n-1):
            left=center/2
            right=left+(center%2)
            while left>=0 and right<n and s[left]==s[right]:
                ans+=1
                left-=1
                right+=1
        return ans

【Manacher's Algorithm 馬拉車算法】
算法說明

def countSubstrings(self, S):
    def manachers(S):
        A = '@#' + '#'.join(S) + '#$'
        Z = [0] * len(A)
        center = right = 0
        for i in xrange(1, len(A) - 1):
            if i < right:
                Z[i] = min(right - i, Z[2 * center - i])
            while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
                Z[i] += 1
            if i + Z[i] > right:
                center, right = i, i + Z[i]
        return Z

    return sum((v+1)/2 for v in manachers(S))