将字符串拆分为两个最长的回文

Question

所以我有这个字符串 "nmmaddammhelloollehdertr"，如果我们将字符串拆分为 x = "nmmaddamm" 和 y = "helloollehdertr"，我们可以找到 LPS 为 x = "mmaddamm" 和 y = "helloolleh".我们知道这是最大的回文，因为 x 的长度为 8，而 y 的长度为 10。 10 * 8 = 80

我尝试使用最长回文子序列的动态规划来解决这个问题，并指出我需要在一个轴心点处拆分字符串，从而创建两个长度最长的字符串。

一种蛮力方法是为每个子序列尝试每个回文，这就是我的尝试：

using System;

namespace Palindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(GetLongestPalindrome("nmmaddammhelloollehdertr"));
        }

        static int GetLongestPalindrome(string s)
        {
            int longest = 1;
            for (int i = 0; i < s.Length; ++i)
                longest = Math.Max(longest, GetLongestPalindromeHelper(s.Substring(0, i)) * GetLongestPalindromeHelper(s.Substring(i)));
            return longest;
        }

        static int GetLongestPalindromeHelper(string str)
        {
            if (str.Length == 0)
                return 1;

            /*
             * For a str = "madeam"
             *       || 0 | 1 | 2 | 3 | 4 | 5 ||
             *  _____|| m | a | d | e | a | m ||
             * | 0 m || 1 | 1 | 1 | 1 | 1 |_5_||
             * | 1 a || 0 | 1 | 1 | 1 |_3_| 3 ||
             * | 2 d || 0 | 0 |_1_| 1 | 1 | 1 ||
             * | 3 e || 0 | 0 | 0 | 1 | 1 | 1 ||
             * | 4 a || 0 | 0 | 0 | 0 | 1 | 1 ||
             * | 5 m || 0 | 0 | 0 | 0 | 0 | 1 ||
             * 
             */
            int[,] matrix = new int[str.Length, str.Length];

            // i -> row
            // j -> column
            // windowSize -> the numbers of chars in the window

            // each character is a palindrome with a length 1
            for (int i = 0; i < str.Length; ++i)
                matrix[i, i] = 1;

            // we handled windowSize 1, so we start at 2
            for (int windowSize = 2; windowSize <= str.Length; ++windowSize)
            {
                for (int i = 0, j = windowSize - 1; i < str.Length - windowSize + 1; ++i, j = i + windowSize - 1)
                {
                    if (str[i] == str[j])
                        matrix[i, j] = matrix[i + 1, j - 1] + 2;
                    else
                        matrix[i, j] = Math.Max(matrix[i, j - 1], matrix[i + 1, j]);
                }
            }

            return matrix[0, str.Length - 1];
        }
    }
}

不过，我确信有更好的方法来做到这一点，但我不知道如何做。有什么建议吗？另外，任何人都可以指出我的代码的复杂性是什么？

谢谢！

Answer 1

你可以在线性时间内做Manacher's Algorithm，得到所有回文的长度。之后，您可以处理长度以从左侧和右侧获得最大长度，然后通过最后一个循环，您可以得到答案。
总复杂度为 O(n).
Manacher 算法有许多有用的资源，包括以下链接： good explanation, Animation

static void Main(String[] args) {
    string s = "nmmaddammhelloollehdertr";
    long ans = Manacher(s, s.Length);
    Console.WriteLine(ans);
}
static long Manacher(string s, int N) {
    int i, j, k, rp;
    int[,] R = new int[2, N + 1];
    // rp is the palindrome radius
    // R is a table for storing results (2 rows for even and odd length palindromes)

    // store the maximum length of the palindromes from left and from right here
    int[] MaxFromLeft = new int[N];
    int[] MaxFromRight = new int[N];
    for (i = 0; i < N; i++) {
        MaxFromLeft[i] = 1;
        MaxFromRight[i] = 1;
    }

    // insert guards to iterate easily 
    // without having to check going out of index range
    s = "@" + s + "#";

    for (j = 0; j <= 1; j++) {
        R[j, 0] = rp = 0; i = 1;
        while (i <= N) {
            while (s[i - rp - 1] == s[i + j + rp]) rp++;
            R[j, i] = rp;
            k = 1;
            while ((R[j, i - k] != rp - k) && (k < rp)) {
                R[j, i + k] = Math.Min(R[j, i - k], rp - k);
                k++;
            }
            rp = Math.Max(rp - k, 0);
            i += k;
        }
    }

    s = s.Substring(1, N);

    int len     // length of the palindrome
        , st    // start index
        , end;  // end index;
    for (i = 1; i <= N; i++) {
        for (j = 0; j <= 1; j++)
            for (rp = R[j, i]; rp > 0; rp--) {
                len = 2 * rp + j;
                st = i - rp - 1;
                end = st + len - 1;
                // update the maximum length
                MaxFromRight[st] = Math.Max(MaxFromRight[st], len);
                MaxFromLeft[end] = Math.Max(MaxFromLeft[end], len);
            }
    }

    // get the accumulative maximums 
    // to avoid doing a second loop inside
    for (i = N - 2, j = 1; i > 1; i--, j++) {
        MaxFromRight[i] = Math.Max(MaxFromRight[i], MaxFromRight[i + 1]);
        MaxFromLeft[j] = Math.Max(MaxFromLeft[j], MaxFromLeft[j - 1]);
    }

    long ans = 0;
    for (i = 0; i < N - 1; i++) {
        ans = Math.Max(ans, MaxFromLeft[i] * MaxFromRight[i + 1]);
    }
    return ans;
}

将字符串拆分为两个最长的回文

Split string into two longest palindrome

c#

algorithm

split

palindrome

subsequence