c# - 最长的唯一回文

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();