如何高效地确定给定字符串中最长的回文字符？

Question

给定一个长度为N的字符串，包含字符[A-Z]，如何确定每个字符的最长回文子串？

我将用一个例子来说明：

给定字符串：JOHNOLSON 在分析字符串时，我们发现有一个以字符O为中心的回文子串，使得字符串看起来像JOHNOLSON。 O的回文子串长度为7，实际上看起来像O--O--O。此外，注意到有一个以N为中心的回文子串，但它只有长度6。

另一个例子， 给定字符串：ABCJOHNOLSON与上面的结果相同，O的回文子串长度为7，看起来像O--O--O。

然而，在给定字符串ABCJOHNOLSONDA中，最长的单个字符回文子串长度为14，字符为A，看起来像A------------A。

其他简单的例子包括： ABA --> A-A（长度3） ABAXYZ --> A-A（长度3） ABAXYZA --> A---A（长度5），而不是长度7，因为A-A---A不是字母A的回文子串。

特别注意最后一个例子，因为它展示了问题的微妙之处。

- jbranchaud

---

你所寻找的词汇应该不是"回文"，因为你举的大多数例子并不是回文。 - Blastfurnace

考虑一个示例字符串ABCDAEEALMNA，当考虑A时，它看起来像A---A--A---A，这是一个大小为12的回文（当您忽略其余字符的唯一性时），但是考虑字符串ABCDAEEALMNOA，整个字符串不再是回文，而是一个更小的子字符串成为最长回文，即长度为5的末尾的A---A。 - jbranchaud

我理解你感兴趣的“模式”，但它并不符合回文的词典定义。我想知道是否有一个正则表达式的解决方案适用于你所寻求的内容。 - Blastfurnace

@BlastFurnace 我明白你的意思。你会建议另一种思考这个问题的方式吗？对我来说，它呈现为回文，所以我不确定它还能被描述成什么。 - jbranchaud

Answer 1

您可以使用线性时间完成此操作，详见此处，附有代码示例。

- Jordan Bentley

Answer 2

这是我想出来的，但我不知道它有多高效。

对于字母表中的每个字母，
    找到该字母的第一个和最后一个出现位置。
    当该字母的子字符串不是回文时（易于检查），
    找到两侧的下一个字母，以便检查每种可能的组合。取最长的并存储它。
取最长的那个。

- Ry-

---

当你说在两侧找到下一个字母，是指当前搜索的字符的下一个实例吗？这对于某些字符串将失败，例如“ABAAACAA”。 - Jordan Bentley

@JordanBentley：不，我的意思是（例如）尝试0.7，然后是0.6，然后是0.4，然后是0.3，然后是0.2，然后是0.0，然后是2.7，然后是2.6，然后是2.4，然后是2.3，然后是2.2，然后是3.7，然后是3.6......你懂的 :) 但如果在特定条件下立即找到回文，则可以中断。 - Ry-

啊，这样就说得通了。如果我理解正确的话，那么这个方法可以行得通，但最坏情况下的时间复杂度将会是O(n!)。 - Jordan Bentley

@JordanBentley：是的，我想它可能不那么好。无论如何，这是一个选择 :) - Ry-

Answer 3

绝对不是最优的。假设输入字符串全为小写。

using System;
using System.Collections.Generic;

public class LongestPalindrome
{
    public int longest(string s)
    {
        Dictionary<char, List<int>> indices = 
            new Dictionary<char, List<int>>();

        // find all indices for each letter
        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if (!indices.ContainsKey(c)) 
                    indices.Add(c, new List<int>());
            indices[c].Add(i);
        }

        int max = Int32.MinValue;

        for (int i = (int)'a'; i <= (int)'z'; i++)
        {
            char c = (char)i;

            // in case a letter didn't appear at all in the input string
            if (!indices.ContainsKey(c)) continue;

            List<int> indexList = indices[c];

            // in case a letter appeared only once in the input string
            if (indexList.Count == 1) max = Math.Max(max, 1);

            for (int j = 0; j < indexList.Count; j++)
            {
                for (int k = j + 1; k < indexList.Count; k++)
                {
                    int dist = indexList[k] - indexList[j] + 1;
                    string sub = s.Substring(indexList[j], dist);
                    if (isPalendrome(sub, c)) 
                                        max = Math.Max(max, dist);
                }   
            }
        }

        return max;
    }

    bool isPalendrome(string s, char c)
    {
        int i = 0;
        while(i < s.Length - 1 - i) 
        {
            if (s[i] != c && s[s.Length - 1 - i] != c) 
            {
                i++;
                continue;   
            }
            if (s[i] != s[s.Length - 1 - i]) return false;
            i++;
        }
        return true;
    }
}

- SundayMonday