Count Palindromic Substrings

Given a string S, compute the number of its palindromic substrings. A substring is considered palindromic if it reads the same backwards as forwards. In other words, for a substring S[i...j], it is palindromic if:

\(S[i] = S[j]\) and \(dp[i+1][j-1]\)

where \(dp[i+1][j-1]\) is true if the substring S[i+1...j-1] is a palindrome. Use an efficient algorithm (such as dynamic programming) to solve this problem.

inputFormat

The input consists of a single line containing the string S.

outputFormat

Output a single integer denoting the number of palindromic substrings in the string.

abba

6