將字符串拆分爲兩個最長的迴文

Question

所以我有這個字符串"nmmaddammhelloollehdertr"，如果我們將字符串拆分爲x = "nmmaddamm"和y = "helloollehdertr"我們可以找到LPS爲x = "mmaddamm"和y = "helloolleh"。我們知道，這是最大的迴文作爲x有8的長度，y有10的長度。 10 * 8 = 80

我試圖通過使用Longest Palindromic子序列的動態編程來解決這個問題，注意到我需要在創建兩個字符串時創建兩個最長的字符串。

蠻力的方法是嘗試對每個子序列的每一個迴文，這是我的嘗試：

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; 
}