Count of palindromes that can be obtained by concatenating equal length prefix and substrings | C ++ program 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPalindromes ( string S ) { int N = ( int ) S . length ( ) ; vector < int > Z ( N ) ; int l = 0 , r = 0 ; for ( int i = 1 ; i < N ; i ++ ) { if ( i <= r ) Z [ i ] = min ( r - i + 1 , Z [ i - l ] ) ; while ( i + Z [ i ] < N && S [ Z [ i ] ] == S [ 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 . size ( ) ; i ++ ) { sum += Z [ i ] + 1 ; } return sum ; } int main ( ) { string S = " abab " ; cout << countPalindromes ( S ) ; return 0 ; }