给定一个字符串,求出该字符串有多少子串是回文串。

回文串:字符串倒序写出来和该字符串相同。比如aba,倒序写出来也是aba,故 aba 是回文串。而 abab 不是回文串,因为倒过来写是 baba。

对于 50%的数据,字符串长度不超过 500; 对于 70%的数据,字符串长度不超过 2000;

对于 100%的数据,字符串长度不超过 500000。[这篇文章是求最长的回文串的,那么如何求回文串的数目呢?可以发现manacher 算法将每个位置为中心能延展出的最长回文串求出来了,那么这个最长回文串的一半(上取整) 就是以该点作为中心的回文串数目。]

++now;