class Solution {
public:
long long maxProduct(string s) {
}
};
1960. 两个回文子字符串长度的最大乘积
给你一个下标从 0 开始的字符串 s ，你需要找到两个 不重叠的回文 子字符串，它们的长度都必须为 奇数 ，使得它们长度的乘积最大。
更正式地，你想要选择四个整数 i ，j ，k ，l ，使得 0 <= i <= j < k <= l < s.length ，且子字符串 s[i...j] 和 s[k...l] 都是回文串且长度为奇数。s[i...j] 表示下标从 i 到 j 且 包含 两端下标的子字符串。
请你返回两个不重叠回文子字符串长度的 最大 乘积。
回文字符串 指的是一个从前往后读和从后往前读一模一样的字符串。子字符串 指的是一个字符串中一段连续字符。
示例 1：
输入：s = "ababbb" 输出：9 解释：子字符串 "aba" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。
示例 2：
输入：s = "zaaaxbbby" 输出：9 解释：子字符串 "aaa" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。
提示：
2 <= s.length <= 105s 只包含小写英文字母。原站题解
python3 解法, 执行用时: 1328 ms, 内存消耗: 34.7 MB, 提交时间: 2023-07-12 10:20:29
class Manacher:
'''
马拉车算法O(n)
计算字符串的所有回文信息
https://oi-wiki.org/string/manacher/
'''
def __init__(self,s):
self.s = s
self.n = len(s)
def get_odd(self):
'''
获取每个中心点的奇回文半径
'''
# Python Version
d1 = [0] * self.n
l, r = 0, -1
for i in range(0, self.n):
k = 1 if i > r else min(d1[l + r - i], r - i + 1)
while 0 <= i - k and i + k < self.n and self.s[i - k] == self.s[i + k]:
k += 1
d1[i] = k
k -= 1
if i + k > r:
l = i - k
r = i + k
return d1
def get_even(self):
'''
获取每个中心点的偶回文半径
'''
# Python Version
d2 = [0] * self.n
l, r = 0, -1
for i in range(0, self.n):
k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
while 0 <= i - k - 1 and i + k < self.n and self.s[i - k - 1] == self.s[i + k]:
k += 1
d2[i] = k
k -= 1
if i + k > r:
l = i - k - 1
r = i + k
return d2
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
ma1 = Manacher(s)
d1 = ma1.get_odd()
pre = [0]*n #pre[i]: s[:i]中的最长奇回文半径
suf = [0]*n #odd[i]: s[i:]中的最长奇回文半径
premax = 1
sufmax = 1
dq1 = deque()
dq2 = deque()
for i in range(n-1):
j = n-i-1
dq1.append((i,d1[i]))
while dq1[0][0]+dq1[0][1]-1<i:
dq1.popleft()
premax = max(premax,i - dq1[0][0] + 1)
dq2.append((j,d1[j]))
while dq2[0][0]-dq2[0][1]+1>j:
dq2.popleft()
sufmax = max(sufmax,dq2[0][0] - j + 1)
pre[i+1] = premax
suf[j] = sufmax
ans = 0
#枚举分界点
for i in range(1,n):
m1 = pre[i]*2-1
m2 = suf[i]*2-1
ans = max(ans,m1*m2)
return ans
cpp 解法, 执行用时: 100 ms, 内存消耗: 21.8 MB, 提交时间: 2023-07-12 10:18:24
class Solution {
public:
long long maxProduct(string s) {
int n = s.size();
vector<int> len(n);
// 马拉车算法 求出以 i 为中心的最大扩展长度
for(int i = 0, j = -1, mx = -1; i < n; ++i) {
if(i > mx)
len[i] = 0;
else
len[i] = min(len[2*j - i], mx - i);
// 中心扩展
while(i - len[i] - 1 >= 0 && i + len[i] + 1 < n && s[i - len[i] - 1] == s[i + len[i] + 1])
++len[i];
if(i + len[i] > mx)
mx = i + len[i], j = i;
}
vector<int> left(n) /* s[0...i] 的最长奇数回文子串 */, right(n) /* s[i...n-1] 的最长奇数回文子串 */;
// 求出 s[0...i] 的最长奇数回文子串
left[0] = 1;
for(int i = 1, p = 0; i < n; ++i) {
while(p + len[p] < i) ++p;
left[i] = max(left[i - 1], 2 * (i - p) + 1);
}
// 求出 s[i...n-1] 的最长奇数回文子串
right[n-1] = 1;
for(int i = n-2, p = n-1; i >= 0; --i) {
while(p - len[p] > i) --p;
right[i] = max(right[i + 1], 2*(p - i) + 1);
}
// 最终结果
long long ret = 0;
for(int i = 0; i + 1 < n; ++i)
ret = max(ret, 1ll * left[i] * right[i + 1]);
return ret;
}
};
golang 解法, 执行用时: 24 ms, 内存消耗: 8.8 MB, 提交时间: 2023-07-12 10:16:51
// 由于本题只要奇回文串，故不需要将s改造
func maxProduct(s string) int64 {
n := len(s)
halfLen := make([]int, n)
for i, mid, r := 0, 0, 0; i < n; i++ {
hl := 1
if i < r {
hl = min(halfLen[mid*2-i], r-i)
}
for ; i >= hl && i+hl < n && s[i-hl] == s[i+hl]; hl++ {}
if i+hl > r {
mid, r = i, i+hl
}
halfLen[i] = hl
}
startPL := make([]int, n)
endPL := make([]int, n)
for i, hl := range halfLen {
left, right := i-hl+1, i+hl-1
startPL[left] = max(startPL[left], hl*2-1)
endPL[right] = max(endPL[right], hl*2-1)
}
for i := 1; i < n; i++ {
startPL[i] = max(startPL[i], startPL[i-1]-2)
}
for i := n - 2; i >= 0; i-- {
startPL[i] = max(startPL[i], startPL[i+1])
}
for i := n - 2; i >= 0; i-- {
endPL[i] = max(endPL[i], endPL[i+1]-2)
}
for i := 1; i < n; i++ {
endPL[i] = max(endPL[i], endPL[i-1])
}
ans := 0
for i := 1; i < n; i++ {
ans = max(ans, endPL[i-1]*startPL[i])
}
return int64(ans)
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
golang 解法, 执行用时: 24 ms, 内存消耗: 9 MB, 提交时间: 2023-07-12 10:15:55
// 马拉车算法
func maxProduct(s string) int64 {
n := len(s)
// 将 s 改造为 t，这样就不需要分 len(s) 的奇偶来讨论了，因为新串 t 的每个回文子串都是奇回文串（都有回文中心）
// s 和 t 的下标转换关系：
// (si+1)*2 = ti
// ti/2-1 = si
t := append(make([]byte, 0, n*2+3), '^')
for _, c := range s {
t = append(t, '#', byte(c))
}
t = append(t, '#', '$')
// 定义一个奇回文串的半长度=(长度+1)/2，即保留回文中心，去掉一侧后的剩余字符串的长度
// halfLen[i] 表示在 t 上的以 t[i] 为回文中心的最长回文子串的半长度
// 即 [i-halfLen[i]+1,i+halfLen[i]-1] 是 t 上的一个回文子串
halfLen := make([]int, len(t)-2)
halfLen[1] = 1
// r 表示当前右边界下标最大的回文子串的右边界下标+1
// mid 为该回文子串的中心位置，二者的关系为 r=mid+halfLen[mid]
for i, mid, r := 2, 1, 0; i < len(halfLen); i++ { // 循环的起止位置对应着原串的首尾字符
hl := 1
if i < r {
// 记 i 关于 mid 的对称位置 i'=mid*2-i
// 若以 i' 为中心的最长回文子串范围超出了以 mid 为中心的回文串的范围（即 i+halfLen[i'] >= r）
// 则 halfLen[i] 应先初始化为已知的半长度 r-i，然后再继续暴力匹配
// 否则 halfLen[i] 与 halfLen[i'] 相等
hl = min(halfLen[mid*2-i], r-i)
}
// 暴力扩展
// 算法的复杂度取决于这部分执行的次数
// 由于扩展之后 r 必然会更新（右移），且扩展的的次数就是 r 右移的次数
// 因此算法的复杂度和 t 的长度成正比
for ; t[i-hl] == t[i+hl]; hl++ {}
if i+hl > r {
mid, r = i, i+hl
}
halfLen[i] = hl
}
// 计算两个数组，其中
// startPL[i] 表示以 s[i] 为首字母的最长奇回文子串的长度
// endPL[i] 表示以 s[i] 为尾字母的最长奇回文子串的长度
startPL := make([]int, n)
endPL := make([]int, n)
for i := 2; i < len(halfLen); i += 2 { // 由于求的是奇数长度，写成 i+=2，改成 i++ 就是不限奇偶
// t 中回文子串的长度为 hl*2-1
// 由于其中 # 的数量总是比字符的数量多 1
// 因此其在 s 中对应的回文子串的长度为 hl-1
// 由于 t 中回文子串的首尾字母一定是 #，再根据上面说的下标转换关系，可以得到其在 s 中对应的回文子串的区间：
// [(i-hl)/2, (i+hl)/2-2]
hl := halfLen[i]
left, right := (i-hl)/2, (i+hl)/2-2
startPL[left] = max(startPL[left], hl-1)
endPL[right] = max(endPL[right], hl-1)
}
for i := 1; i < n; i++ {
startPL[i] = max(startPL[i], startPL[i-1]-2) // startPL[i] 还可能是一个更长的回文串缩短后的结果
}
for i := n - 2; i >= 0; i-- {
startPL[i] = max(startPL[i], startPL[i+1]) // 变成后缀最大值
}
for i := n - 2; i >= 0; i-- {
endPL[i] = max(endPL[i], endPL[i+1]-2) // endPL[i] 还可能是一个更长的回文串缩短后的结果
}
for i := 1; i < n; i++ {
endPL[i] = max(endPL[i], endPL[i-1]) // 变成前缀最大值
}
ans := 0
for i := 1; i < n; i++ {
ans = max(ans, endPL[i-1]*startPL[i])
}
return int64(ans)
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }