原文链接：OIwiki

描述

给定一个长度为 n 的字符串 ，请找到所有对 (i, j) 使得子串 s[i...j] 为一个回文串。

解法

不能发现，如果s是回文串，那么s的所有回文串个数等于s的回文半径，因此，求回文串个数等价于求最长回文串半径。

设d[i]表示以i为对称中心的回文串个数。

为了快速计算，我们可以维护已找到的最靠右的子回文串的边界(l，r)。初始令l = 0 ， r = -1。

1.如果i > r，那么我们直接暴力计算出d[i]，并更新(l，r)。

2.如果i ≤ r, 假设j = l + (r - i)，此时 j 与 i 在当前这个子回文串中对称。

　　2.1 如果 l ≤ j - d[j], 那么我们可以先令d[i] = d[j], 然后再继续暴力增大d[i]

　　2.2 如果 j - d[j] < l, 我们可以令d[i] = r - i, 然后继续计算。

不难发现每一次计算，都会使得 r 增大1，而r最大为n，故时间复杂度为O(n)