Readme

1960.Maximum-Product-of-the-Length-of-Two-Palindromic-Substrings

此题的第一部分是Manacher算法，用o(N)的时间计算所有回文串的长度（考虑每个字符作为回文串的中心）。具体的算法参见LC 005.Longest-Palindromic-Substring.

Manacher算法的输出是数组P[i]，表示以i为中心，可以构造最长长度为P[i]*2+1的回文串。注意，这个回文串的长度必然是奇数。

单本题接下来的部分也很关键。我们如何遍历两个互不相交的回文串。一个比较自然的想法就是用前缀、后缀数组。令left[i]表示s[0:i]里的最长回文串长度、right[i]表示s[i:n-1]里的最长回文串长度，那么最终答案就是遍历i寻找最大的left[i]*right[i+1]即可。

现在来想left[i]怎么求。显然left[i]必然会继承于left[i-1]. 其次我们还要考虑那些包括了s[i]的回文串。所以我们其实要找的是最小的位置j，使得以j为中心的回文串能覆盖到i。这样以j为中心、长度为(i-j)*2+1的字符串是left[i]所没有覆盖到的、最长的一个回文串。这个j怎么找呢？我们其实只要从小到大顺着过一遍，当恰好j+P[j]>=i时停下来即可。此外我们还发现，当我们从小到大考察i时，j的考察方向也是单调递增的。所以意味着我们用o(N)的时间就可以把left[i]数组求出来。

类似地我们可以求出right[i]和最终的答案。