为给定字符串的所有前缀查找最长回文子字符串的长度

Question

我已经解决了寻找最长回文子串的问题，但这是不同的。给定类似于"字符串"的字符串；ababa"；，所有的最长回文子串的长度前缀如下-

• "a"："a"；(长度1(
• "ab"："a"；或"；b"；(长度1(
• "aba"："aba"；(长度3(
• "abab"："aba"；或"；bab"；(长度3(
• "ababa"："ababa"；(长度5(

这是示例输入/输出->

• 样本输入："；ababa">
• 样本输出：1 1 3 3 5

我考虑了几个解决方案-

1. 找出给定字符串的所有回文子串(O(N^2(使用围绕中心展开的方法(，然后对于每个前缀，找出它是否包含子串(按长度降序排序(。这似乎比O(N^3(更糟糕
2. 对于每个前缀，使用Manacher算法(O(N((找到最长的回文子串。将有N个前缀，所以这是O(N^2(

我们只需要长度，而不需要实际的回文。有没有什么更容易/更好的方法(就运行时复杂性而言(让我错过了？

更新：我们需要字符串的所有前缀的长度(最长回文子字符串的长度((就像上面的例子一样(。

Answer 1

第二个选项。想想马纳彻是怎么工作的。每次它移动右指针时，基本上都会考虑一个新的前缀。在每次迭代中，跟踪管理器表值的当前计算部分的最大值，即当前前缀的最长回文子序列的长度(以右指针结束(。这需要O(n(时间。

Answer 2

我建议使用此解决方案：https://www.geeksforgeeks.org/longest-palindromic-substring-set-2/?ref=rp，其时间复杂度为O(N^2(，空间复杂度为0(1(。但在您的情况下，您需要一个数组(maxArr(来保存前缀的最大长度子字符串的长度

想法是一样的，你选择一个中心，并找到最大长度的子串，以它为中心。在最大子字符串将结束的位置，更新该位置的数组中的最大长度。最后，数组中的一些位置(maxArr(可能为空，这些位置将与它们的左侧位置保持相同的值。

Answer 3

这里有一个解决方案：

public static int[] solve(String S) {
int n = S.length();
boolean[][] palindromeDP = new boolean[n][n];
int[][] lengthDP = new int[n][n];
for(int i=0;i<n;i++) {
// single letter are palindrome
palindromeDP[i][i] = true;
lengthDP[i][i] = 1;
}
for(int i=1;i<n;i++) {
// two letter palindrome (i and i-1)
if(S.charAt(i-1) == S.charAt(i)) {
palindromeDP[i-1][i] = true;
lengthDP[i-1][i] = 2;
} else {
palindromeDP[i-1][i] = false;
lengthDP[i-1][i] = 1;
}
}
for(int i=2;i<n;i++) {
for(int j=0; j<n-i;j++) {
// string[j:i]
if(palindromeDP[j + 1][j + i - 1] && (S.charAt(j+i) == S.charAt(j))) {
// middle is palindrome and side letter are equal, it's a palindrome
// add two more in length of the new side letters
palindromeDP[j][j+i] = true;
lengthDP[j][j+i] = lengthDP[j + 1][j + i - 1] + 2;
} else {
// remains same till now
palindromeDP[j][j+i] = false;
lengthDP[j][j+i] = lengthDP[j + 1][j + i - 1];
}
}
}
int[] result = new int[n];
int maxTillNow = 1;
for(int i=0;i<n;i++) {
if(maxTillNow < lengthDP[0][i]) {
maxTillNow = lengthDP[0][i];
}
result[i] = maxTillNow;
}
return result;
}

Answer 4

package code.shubham;
import java.util.Arrays;
public class LongestPalindromicSubstringForEachPrefix {
class Solution {
int[] solve(String s) {
int[] dp = new int[s.length()];
lps(s, dp);
for (int i = 1; i < s.length(); i++)
dp[i] = Math.max(dp[i], dp[i-1]);
return dp;
}
void lps(String s, int[] dp) {
for (int  i = 0; i < s.length(); i++) {
expand(s, i, i, dp);
expand(s, i, i + 1, dp);
}
}
int expand(String s, int l , int r, int[] dp) {
while (l > -1 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
l++;
r--;
dp[r] = Math.max(dp[r], r - l + 1);
return r - l + 1;
}
}
public static void main(String[] args) {
Arrays.stream(
new LongestPalindromicSubstringForEachPrefix(). new Solution().solve("abaaabbbaa")
).forEach(e -> System.out.print(e + " "));
}
}