File tree Expand file tree Collapse file tree 1 file changed +2
-2
lines changed
String/1960.Maximum-Product-of-the-Length-of-Two-Palindromic-Substrings Expand file tree Collapse file tree 1 file changed +2
-2
lines changed Original file line number Diff line number Diff line change 22
33此题的第一部分是Manacher算法，用o(N)的时间计算所有回文串的长度（考虑每个字符作为回文串的中心）。具体的算法参见``` LC 005.Longest-Palindromic-Substring ``` .
44
5- Manacher算法的输出是数组len [ i] ，表示以i为中心，可以构造最长长度为``` len [i]*2- 1``` 的回文串。注意，这个回文串的长度必然是奇数。
5+ Manacher算法的输出是数组P [ i] ，表示以i为中心，可以构造最长长度为``` P [i]*2+ 1``` 的回文串。注意，这个回文串的长度必然是奇数。
66
77单本题接下来的部分也很关键。我们如何遍历两个互不相交的回文串。一个比较自然的想法就是用前缀、后缀数组。令left[ i] 表示s[ 0: i ] 里的最长回文串长度、right[ i] 表示s[ i: n-1 ] 里的最长回文串长度，那么最终答案就是遍历i寻找最大的``` left[i]*right[i+1] ``` 即可。
88
9- 现在来想left[ i] 怎么求。显然left[ i] 必然会继承于left[ i-1] . 其次我们还要考虑那些包括了s[ i] 的回文串。所以我们其实要找的是最小的位置j，使得以j为中心的回文串能覆盖到i。这样以j为中心、长度为``` (i-j)*2+1 ``` 的字符串是left[ i] 所没有覆盖到的、最长的一个回文串。这个j怎么找呢？我们其实只要从小到大顺着过一遍，当恰好``` j+len [j]-1 >=i ``` 时停下来即可。此外我们还发现，当我们从小到大考察i时，j的考察方向也是单调递增的。所以意味着我们用o(N)的时间就可以把left[ i] 数组求出来。
9+ 现在来想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] 数组求出来。
1010
1111类似地我们可以求出right[ i] 和最终的答案。
You can’t perform that action at this time.
0 commit comments