Count of palindromes that can be obtained by concatenating equal length prefix and substrings | Java program for the above approach ; Function to calculate the number of palindromes ; Calculation of Z - array ; Calculation of sigma ( Z [ i ] + 1 ) ; Return the count ; Driver Code ; Given String
import java . util . * ; class GFG { static int countPalindromes ( String S ) { int N = ( int ) S . length ( ) ; int [ ] Z = new int [ ( N ) ] ; int l = 0 , r = 0 ; for ( int i = 1 ; i < N ; i ++ ) { if ( i <= r ) Z [ i ] = Math . min ( r - i + 1 , Z [ i - l ] ) ; while ( i + Z [ i ] < N && S . charAt ( Z [ i ] ) == S . charAt ( i + Z [ i ] ) ) { Z [ i ] ++ ; } if ( i + Z [ i ] - 1 > r ) { l = i ; r = i + Z [ i ] - 1 ; } } int sum = 0 ; for ( int i = 0 ; i < Z . length ; i ++ ) { sum += Z [ i ] + 1 ; } return sum ; } public static void main ( String [ ] args ) { String S = " abab " ; System . out . println ( countPalindromes ( S ) ) ; } }