How to find the longest palindrome in a given string?

Question

Possible Duplicate:
Write a function that returns the longest palindrome in a given string

I know how to do this in O(n^2). But it seems like there exist a better solution.

I've found this, and there is a link to O(n) answer, but it's written in Haskell and not clear for me.

It would be great to get an answer in c# or similar.

Solution 1

I've found clear explanation of the solution here. Thanks to Justin for this link.

There you can find Python and Java implementations of the algorithm (C++ implementation contains errors).

And here is C# implementation that is just a translation of those algorithms.

public static int LongestPalindrome(string seq)
    {
        int Longest = 0;
        List<int> l = new List<int>();
        int i = 0;
        int palLen = 0;
        int s = 0;
        int e = 0;
        while (i<seq.Length)
        {
            if (i > palLen && seq[i-palLen-1] == seq[i])
            {
                palLen += 2;
                i += 1;
                continue;
            }
            l.Add(palLen);
            Longest = Math.Max(Longest, palLen);
            s = l.Count - 2;
            e = s - palLen;
            bool found = false;
            for (int j = s; j > e; j--)
            {
                int d = j - e - 1;
                if (l[j] == d)
                {
                    palLen = d;
                    found = true;
                    break;
                }
                l.Add(Math.Min(d, l[j]));
            }
            if (!found)
            {
                palLen = 1;
                i += 1;
            }
        }
        l.Add(palLen);
        Longest = Math.Max(Longest, palLen);
        return Longest;
    }

Solution 2

And this is its java version:

public static int LongestPalindrome(String seq) {
    int Longest = 0;
    List<Integer> l = new ArrayList<Integer>();
    int i = 0;
    int palLen = 0;
    int s = 0;
    int e = 0;

    while (i < seq.length()) {
        if (i > palLen && seq.charAt(i - palLen - 1) == seq.charAt(i)) {
            palLen += 2;
            i += 1;
            continue;
        }
        l.add(palLen);
        Longest = Math.max(Longest, palLen);
        s = l.size() - 2;
        e = s - palLen;
        boolean found = false;
        for (int j = s; j > e; j--) {
            int d = j - e - 1;
            if (l.get(j) == d) {
                palLen = d;
                found = true;
                break;
            }
            l.add(Math.min(d, l.get(j)));
        }
        if (!found) {
            palLen = 1;
            i += 1;
        }
    }
    l.add(palLen);
    Longest = Math.max(Longest, palLen);
    return Longest;
}