[Algorithm] Find the Number of Palindrome in a String

You are given a string, count the number of palindrome in it.

A very naive solution is to enumerate all possible substrings and check if they are palindrome or not. The time complexity would be O(n^3). A better way is to use each one character and two continue characters as the center of the palindrome and expand to left and right. The time complexity would be O(nk) where k is the longest radix of palindrome. The worst case would be O(n^2). If we use DP method to find all palindrome, as mentioned in my prior post, the time complexity would be O(n^2). The best way is to use Manacher algorithm to find all possible palindrome and then count the number, which would give O(n) time complexity.

import java.util.*;

public class CountTheNumberofPalindrome {
 private static String process(String s) {
  StringBuffer sb = new StringBuffer();
  sb.append('#');
  for(int i = 0; i < s.length(); i++) {
   sb.append(s.charAt(i));
   sb.append('#');
  }
  return sb.toString();
 }

 private static int[] Manacher(String s) {
  String ns = process(s);
  int[] P = new int[ns.length()];
  int C = 0, R = 0;
  for(int i = 0; i < ns.length(); i++) {
   int mirror = 2*C - i;
   P[i] = R > i ? Math.min(R-i, P[mirror]) : 0;

   while(i+P[i]+1 < ns.length() && i-P[i]-1 >= 0 && ns.charAt(i+P[i]+1) == ns.charAt(i-P[i]-1))
    P[i]++;

   if(i+P[i] > R) {
    C = i;
    R = i + P[i];
   }
  }
  return P;
 }

 public static int count(String s) {
  int[] P = Manacher(s);
  int cnt = 0;
  for(int i = 0; i < P.length; i++) {
   cnt  = cnt + (P[i] + 1) / 2;
  }
  return cnt;
 }

 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   System.out.println(count(scan.next()));
  }
 }
}