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

Question

我已经解决了寻找最长回文子串的问题，但这是不同的。 给定一个像“ababa”这样的字符串，all前缀的最长回文子串的长度将如下 -

• “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

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

Answer 2

我建议这个解决方案：https://www.geeksforgeeks.org/longest-palindromic-substring-set-2/?ref=rp，它的时间复杂度是 O(N^2) ，空间复杂度是 O( 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 + " "));
    }

}