Count Palindromic Substrings

Given a string s consisting of lowercase alphabetic characters, count the total number of palindromic substrings in s. A substring is considered palindromic if it reads the same backward as forward. For example, in the string abba there are 6 palindromic substrings. Use an efficient approach that expands around potential centers.

The underlying idea is to use the expansion technique, considering every index (and every gap between two indices) as the potential center of a palindrome. More formally, for a given string of length n, you should compute the result by summing, for each index i, the number of palindromes centered at i (odd length) and the number of palindromes centered between i and i+1 (even length). This can be described using the formula:

\[ \text{result} = \sum_{i=0}^{n-1} \Big( P(i,i) + P(i,i+1) \Big) \]

where \(P(left, right)\) is the number of palindromic substrings expanded around the center(s) defined by left and right.

inputFormat

The input is read from standard input and consists of a single line containing the string s.

outputFormat

Output to standard output a single integer representing the number of palindromic substrings in s.

## sample

abba

6

</p>