647. Palindromic Substrings

647. Palindromic Substrings

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.

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:

1. The input string length won't exceed 1000.

-----------------------------
manacher's algorithm。p[i]记录的是以i为中点，最长的回文字符串向左或向右扩张的长度，包括i。也就是把字符串对折之后的长度
注意p[i]的取值，和right的更新
也可以写作

p[i] = Math.min(right - i + 1, p[mirror])

但同时要修改

if (i + p[i] - 1 > right) {
    center = i;
    right = i + p[i] - 1;
}

class Solution {
    public int countSubstrings(String s) {
        String ss = "#";
        for (int i = 0; i < s.length(); i++) {
            ss += s.charAt(i) + "#";
        }
        
        int center = 0;
        int right = 0;
        int[] p = new int[ss.length()];
        
        for (int i = 1; i < ss.length(); i++) {
            int mirror = center - (i - center);

            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            }
            while (i - p[i] >= 0 && p[i] + i < ss.length() && ss.charAt(i + p[i]) == ss.charAt(i - p[i])) {
                p[i]++;
            }
            
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        
        int count = 0;
        for (int i : p) {
            count += i / 2;
        }
        
        return count;
    }
}

同类型的题：http://shibaili.blogspot.com/2013/11/day-51-5-longest-palindromic-substring.html
阅读：https://www.felix021.com/blog/read.php?2040