Palindromes 2

A string is called a palindrome if it reads the same forwards and backwards. For example, abba is a palindrome, while omax is not. For a given string $\alpha$, we denote by $\alpha [i..j]$ its substring starting at the $i$-th position and ending at the $j$-th position (inclusive), with length j - i + 1, where positions are numbered starting from $1$.

Given a string $\alpha$ of length $n$ (1 \leq n \leq 5\,000\,000), determine the number of pairs $(i,j)$ with 1 \leq i < j \leq n such that the substring $\alpha [i..j]$ is a palindrome.