Count Palindromic Substrings

Given a string s, count the number of substrings that are palindromic. A palindrome is a sequence of characters that reads the same backwards as forwards. Note that every single character is considered a palindrome. The problem can be approached using dynamic programming or by expanding around potential centers.

For instance, if s = "abba", its palindromic substrings are: "a", "b", "b", "a", "bb", and "abba", giving a total of 6.

Mathematically, for each center index \( i \) (or center between \( i \) and \( i+1 \)), we count all substrings that expand symmetrically. That is, for each center, while \( s[left] = s[right] \), the substring \( s[left \ldots right] \) is a palindrome.

Your task is to implement a solution that reads a string from standard input and prints out the total number of palindromic substrings to standard output.

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase English letters.

outputFormat

The output is a single integer representing the total number of palindromic substrings present in the string.

abba

6