最長獨特的迴文

Question

我有以下接口

public interface IPalindromeEngine 
{ 
    Palindrome GetLongestPalindrome(string sequence); 

    Task<Palindrome> GetLongestPalindromeAsync(string sequence); 

    List<Palindrome> GetLongestPalindromes(string sequence, int n, bool uniqueOnly); 

    Task<List<Palindrome>> GetLongestPalindromesAsync(string sequence, int n, bool uniqueOnly); 
} 

與http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html採取執行代碼似乎很好的測試（從所有的評論者和實施者）...

/// <summary> 
/// Computes the longest palindromic substring in linear time 
/// using Manacher's algorithm. 
/// 
/// The code is lifted from the following excellent reference 
/// http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html 
/// </summary> 
public class ManacherPalindromeEngine : IPalindromeEngine 
{ 
    // p[i] = length of longest palindromic substring of transform, centered at i. 
    private int[] p; 
    private char[] transform; 
    private string sequence; 

    private void Initialize() 
    { 
     transform = new char[sequence.Length * 2 + 3]; 
     transform[0] = '$'; 
     transform[sequence.Length * 2 + 2] = '@'; 
     for (int i = 0; i < sequence.Length; ++i) 
     { 
      transform[2 * i + 1] = '#'; 
      transform[2 * i + 2] = sequence[i]; 
     } 
     transform[sequence.Length * 2 + 1] = '#'; 
    } 

    private void ExtractPalindromesViaManacher(string sequence) 
    { 
     this.sequence = sequence; 
     Initialize(); 

     int center = 0, right = 0; 
     p = new int[transform.Length]; 
     for (int i = 1; i < transform.Length - 1; i++) 
     { 
      int mirror = 2 * center - i; 

      if (right > i) 
       p[i] = Math.Min(right - i, p[mirror]); 

      // Attempt to expand palindrome centered at i. 
      while (transform[i + (1 + p[i])] == transform[i - (1 + p[i])]) 
       p[i]++; 

      // If palindrome centered at i expands past right, 
      // adjust center based on expanded palindrome. 
      if (i + p[i] > right) 
      { 
       center = i; 
       right = i + p[i]; 
      } 
     } 
    } 

    public Palindrome GetLongestPalindrome(string sequence) 
    { 
     if (String.IsNullOrEmpty(sequence)) 
      return null; 

     ExtractPalindromesViaManacher(sequence); 

     int length = 0; 
     int center = 0; 
     for (int i = 1; i < p.Length - 1; ++i) 
     { 
      if (p[i] > length) 
      { 
       length = p[i]; 
       center = i; 
      } 
     } 
     int startIndex = (center - 1 - length)/2; 
     string s = this.sequence.Substring(startIndex, length); 
     return new Palindrome(s, startIndex); 
    } 

    public Task<Palindrome> GetLongestPalindromeAsync(string sequence) 
    { 
     return Task.Run(() => GetLongestPalindrome(sequence)); 
    } 

    public List<Palindrome> GetLongestPalindromes(string sequence, int n, bool uniqueOnly) 
    { 
     if (String.IsNullOrEmpty(sequence)) 
      return null; 

     ExtractPalindromesViaManacher(sequence); 

     List<Palindrome> palindromes = null; 
     if (uniqueOnly) 
     { 
      palindromes = p 
       .Select((l, i) => new { Length = l, Index = i }) 
       .OrderByDescending(c => c.Length) 
       .Select(c => 
       { 
        int startIndex = (c.Index - 1 - c.Length)/2; 
        string s = this.sequence.Substring(startIndex, c.Length); 
        Trace.WriteLine(startIndex); 
        return new Palindrome(s, startIndex); 
       }) 
       .ToList(); 
      palindromes = palindromes 
       .Distinct(new Palindrome.DuplicateComparer()) 
       .Take(n) 
       .ToList(); 
     } 
     else 
     { 
      palindromes = p 
       .Select((l, i) => new { Length = l, Index = i }) 
       .OrderByDescending(c => c.Length) 
       .Take(n) 
       .Select(c => 
       { 
        int startIndex = (c.Index - 1 - c.Length)/2; 
        string s = this.sequence.Substring(startIndex, c.Length); 
        Trace.WriteLine(startIndex); 
        return new Palindrome(s, startIndex); 
       }) 
       .ToList(); 
     } 
     return palindromes; 
    } 

    public Task<List<Palindrome>> GetLongestPalindromesAsync(string sequence, int n, bool uniqueOnly) 
    { 
     return Task.Run(() => GetLongestPalindromes(sequence, n, uniqueOnly)); 
    } 
} 

與

public class Palindrome 
{ 
    public Palindrome(string sequence, int startIndex) 
    { 
     Sequence = sequence; 

     if (startIndex < 0) 
      throw new ArgumentException("startIndex must be >= 0"); 
     StartIndex = startIndex; 
    } 

    public int StartIndex { get; set; } 

    public int Length 
    { 
     get 
     { 
      if (String.IsNullOrEmpty(Sequence)) 
       return 0; 
      return Sequence.Length; 
     } 
    } 

    public string Sequence { get; } 

    internal class DuplicateComparer : IEqualityComparer<Palindrome> 
    { 
     public bool Equals(Palindrome x, Palindrome y) 
     { 
      return x.Sequence == y.Sequence; 
     } 

     public int GetHashCode(Palindrome obj) 
     { 
      unchecked 
      { 
       int hash = 17; 
       return hash * 23 + obj.Sequence.GetHashCode(); 
      } 
     } 
    } 
} 

現在我已經測試在一些測試用例上編了這個，但有一個案例看起來不正確。即輸入字符串

「weeewweeew」

這將返回的結果：

1. weeewweeew開始：0長度：10
2. weeew開始：0長度：5

3. ee開始：1長度：2

4. 爲什麼我沒有得到字符串「eeewweee」或「eee」？

對代碼質量的任何其他建議將不勝感激。

Answer 1

palindromes = p 
    .Select((l, i) => new { Length = l, Index = i }) 
    .OrderByDescending(c => c.Length) 

此時，對字符串中的每個位置上，所述查詢包含在該位置爲中心的最長迴文的長度。爲了找回所有迴文，你需要用相同的中心，選擇所有迴文的子字符串：

.SelectMany(c => 
{ 
    int startIndex = (c.Index - 1 - c.Length)/2; 
    int numSubPalindromes = (c.Length + 1)/2; 
    Palindrome[] subPalindromes = new Palindrome[numSubPalindromes]; 
    for (int i = 0; i < numSubPalindromes; ++i) { 
     String s = this.sequence.Substring(startIndex + i, c.Length - i * 2); 
     subPalindromes[i] = new Palindrome(s, startIndex + i); 
    } 
    return subPalindromes; 
}) 
.ToList();