Manacher算法（用于在线性时间内查找最长回文子串的算法）

Question

我花了大约6-8个小时来理解Manacher算法，但现在我准备放弃了。但在我放弃前，最后一次尝试，有人能解释一下吗？我不关心代码，我想要有人解释算法。

这里似乎是其他人很喜欢用来解释算法的地方：http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

我明白为什么你想要将字符串转换成例如 '#a#b#b#a#' 的形式。之后我就迷失了。例如，之前提到的网站的作者说算法的关键部分是：

                      if P[ i' ] ≤ R – i,
                      then P[ i ] ← P[ i' ]
                      else P[ i ] ≥ P[ i' ]. (Which we have to expand past 
                      the right edge (R) to find P[ i ])

他/她说P[i]等于5时，如果P[i'] = 7且P[i]不小于或等于R-i，则这似乎是错误的。

如果您对该算法不熟悉，请参考以下链接：http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html（我尝试过这个，但术语很糟糕和令人困惑。首先，有些东西没有定义。此外，变量太多了。您需要一个清单来回忆哪个变量指的是什么。）

另一个链接： http://www.akalin.cx/longest-palindrome-linear-time（祝好运）

该算法的基本思路是在线性时间内找到最长回文子串。使用最少至中等的努力可以将其完成为O(n^2)。这个算法被认为是相当聪明的，因为它将复杂度降低到了O(n)。

- user678392

---

这不是一个答案，而是一个建议。我发现解决类似于难懂的算法之类的问题的最佳技巧之一是向别人解释它，即使你自己并没有完全理解它。所以找个可怜的人坐下来，向他们解释算法。等你讲完之后，你的听众可能会对你感到烦恼，但你应该对这个算法有更深刻的理解了。 - OmnipotentEntity

我试过类似的事情。我坐下来尝试用自己的话写下这个算法。那对我帮助很大。但是我没有进一步深入。 (而且周围没有可怜的傻瓜。) 谢谢你的建议，会记在心中的。 - user678392

你可能会发现这个实现代码 https://gist.github.com/moccaplusplus/10996282 更加详细解释。 - Tomasz Gawel

我完全能够理解你对所找到的“解释”感到沮丧。可能有90%或更多的人在网上都不应该试图向他人解释任何事情；他们只会让对方更加困惑。教学的天赋很难得。 - Abhijit Sarkar

Answer 1

我认同在链接的解释中，逻辑不太正确。下面是我提供的一些详细信息。

Manacher算法填充一个表P[i]，其中包含以i为中心的回文扩展的长度。如果P[5]=3，则在位置5两侧的三个字符属于回文。该算法利用了以下事实：如果你已经找到了一个长的回文，你可以通过查看左侧的P值来快速地填充回文右侧的P值，因为它们应该大部分相同。

我将从解释你所谈论的情况开始，然后根据需要扩展这个答案。

R表示以C为中心的回文的右侧索引。这是您指出的地方的状态：

C=11
R=20
i=15
i'=7
P[i']=7
R-i=5

逻辑如下：

if P[i']<=R-i:  // not true
else: // P[i] is at least 5, but may be greater

链接中的伪代码表明，如果测试失败，则 P[i] 应大于或等于 P[i']，但我认为应该大于或等于 R-i，而且解释也支持这一点。

由于 P[i'] 大于 R-i，以 i' 为中心的回文串超出了以 C 为中心的回文串。我们知道以 i 为中心的回文串至少有 R-i 个字符宽，因为我们在那一点仍然有对称性，但我们必须明确地搜索超出那个点。

如果 P[i'] 不大于 R-i，那么以 i' 为中心的最大回文串在以 C 为中心的最大回文串内，所以我们会知道 P[i] 不能比 P[i'] 更大。如果是，我们将得到一个矛盾。这意味着我们可以扩展以 i 为中心的回文串超过 P[i']，但如果我们能够这样做，那么由于对称性，我们也将能够扩展以 i' 为中心的回文串，但它已经应该尽可能大。

这种情况在先前已有说明：

C=11
R=20
i=13
i'=9
P[i']=1
R-i=7

在这种情况下，P[i']<=R-i。由于我们仍然离以C为中心的回文边缘有7个字符的距离，因此我们知道i周围至少有7个字符与i'周围的7个字符相同。由于i'周围只有一个字符的回文字符串，因此i周围也有一个字符的回文字符串。

j_random_hacker注意到逻辑应该更像是这样的：

if P[i']<R-i then
  P[i]=P[i']
else if P[i']>R-i then
  P[i]=R-i
else P[i]=R-i + expansion

如果 P[i'] < R-i，我们知道 P[i] == P[i']，因为我们仍然在以 C 为中心的回文字符串内部。

如果 P[i'] > R-i，我们知道 P[i] == R-i，否则以 C 为中心的回文字符串将扩展到 R 之外。

因此，只有在特殊情况下 P[i'] == R-i 时才需要扩展，这样我们才能确定 P[i] 处的回文字符串可能更长。

实际代码中通过设置 P[i]=min(P[i'],R-i) 然后始终进行扩展来处理该情况。这种处理方式不会增加时间复杂度，因为如果不需要扩展，则执行扩展所需的时间是恒定的。

- Vaughn Cato

---

+1，但我注意到另一个细节。如果P[i'] < R-i（注意：<，而不是<=），那么根据你提供的原因，必须有P[i] = P[i']。好的，现在考虑P[i'] > R-i的情况：* 必须是P[i] = R-i*。为什么？假设P[i]比这更长：那将意味着T[R + 1] = T[i-（R-i+1）]。但是T[i-（R-i+1）] = T[i' +（R-i+1）]，因为C周围有一个回文；并且T[i' +（R-i+1）] = T[i' -（R-i+1）]，因为以i'为中心至少宽度为R-i + 1的回文（请记住我们假设了P[i'] > R-i）。 i'-（R-i+1）= L-1，所以这意味着T[R + 1] = T[L-1]... - j_random_hacker

@j_random_hacker：是的，我理解。 - Vaughn Cato

感谢您更新您的帖子。我现在已经实现了我建议的算法的C++版本，并针对由3个或更少字母组成且长度最多为1000的5000个单词对明显的O（n ^ 2）算法进行了测试。正如您所说，P [i']> R-i测试实际上并没有节省任何时间，因为如果没有它，下一个回文扩展尝试必然会失败，但重要的是要注意（就像您一样）正确的早期停止测试是P [i'] <R-i而不是P [i'] <= R-i。 - j_random_hacker

@Vaughn Cato，你能解释一下时间复杂度为O(n)的运行时间吗？ - user1436489

@j_random_hacker 自你的留言已经七年了，但我有几个跟进问题，因为 < 和 <= 的区别似乎是算法中最棘手的部分。首先，你说：“_T [i-（R-i+1）] = T [i'+（R-i+1）]，因为在C处有一个回文_” - 我认为这个结论不能基于C处的回文得出，而应该基于i处的回文。其次，你得出了 T [R + 1] = T [L-1]，但没有将其与你的主张 P [i] = P [i'] 关联起来。你是想表明 T [R + 1] = T [L-1] 是一种矛盾，因为那样会使P[C]变大吗？ - Abhijit Sarkar

Answer 2

我在下面的链接中找到了目前为止最好的解释：

http://tarokuriyama.com/projects/palindrome2.php

它还有一个可视化示例，使用了与问题中提到的第一个链接相同的字符串示例（babcbabcbaccba）。

除了这个链接外，我还在下面的链接中找到了代码：

http://algs4.cs.princeton.edu/53substring/Manacher.java.html

我希望这对那些努力理解这个算法核心的人有所帮助。

- scv

---

这些绝对是我在这个页面上见过的最好的资源；在我的桌面上仔细阅读它们，一边对照着看，一切都变得清晰明了。谢谢你！ - undefined

Answer 3

这个网站上的算法在一定程度上是可以理解的。 http://www.akalin.cx/longest-palindrome-linear-time

要理解这种特殊的方法，最好的方法是在纸上尝试解决问题，并捕捉您可以实现的技巧，以避免检查每个可能的中心的回文。

首先问自己 - 当您找到给定长度的回文时，比如说5 - 作为下一步，您不能跳到此回文的末尾（跳过4个字母和4个中间字母）吗？

如果您尝试创建长度为8的回文并放置另一个长度> 8的回文，其中心位于第一个回文的右侧，您会注意到一些有趣的事情。试试看： 长度为8的回文 - WOWILIKEEKIL - Like + ekiL = 8 现在，在大多数情况下，您将能够将两个E之间的位置写下来作为中心，数字8作为长度，并在最后一个L之后跳转以寻找更大回文的中心。

这种方法是不正确的，因为更大回文的中心可能在ekiL内部，如果您在最后一个L之后跳跃，则会错过它。

在找到LIKE+EKIL后，你将8放入这些算法使用的数组中，看起来像这样：

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8]

对于

[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#]

诀窍是你已经知道，在8之后的7个（8-1）数字很可能与左侧相同，所以下一步是自动将左侧的7个数字复制到8的右侧，记住它们还不是最终结果。 数组会变成这样

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3]（我们现在在8这里）

对于

[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#,E,#,K,#,I,#,L]

让我们举个例子，假设这样的跳跃会破坏我们当前的解决方案，看看我们能注意到什么。

WOWILIKEEKIL - 让我们尝试在EKIL内部某处设置更大的回文中心。 但这是不可能的 - 我们需要将EKIL更改为包含回文的内容。 什么？哦，那就是诀窍。 拥有更大的回文中心在我们当前回文的右侧（和左侧）的唯一可能性是它已经在回文的右侧（和左侧）。

让我们尝试基于WOWILIKEEKIL构建一个回文 我们需要将EKIL更改为例如EKIK，并以I作为更大回文的中心 - 记得同时将LIKE更改为KIKE。 我们棘手的回文的第一个字母将是：

WOWIKIKEEKIK

如前所述 - 让最后一个I成为比KIKEEKIK更大的回文中心：

WOWIKIKEEKIKEEKIKIW

让我们制作数组，直到我们的旧回文，并找出如何利用额外的信息。

for

[_ W _ O _ W _ I _ K _ I _ K _ E _ E _ K _ I _ K _ E _ E _ K _ I _ K _ I _ W ]

它将会是 [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8]

我们知道下一个I - 第三个将是最长的回文，但让我们暂时忘记它。让我们从8的左边复制数组中的数字（8个数字）。

[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3]

在我们的循环中，我们在8号数字和E之间。I（最大回文的未来中心）有什么特别之处，我们不能直接跳到K（当前最大回文的最后一个字母）？特别之处在于它超过了当前数组的大小...怎么做呢？如果你向右移动3个空格，就会超出数组范围。这意味着它可以成为最大回文的中心，而你能够跳跃的最远距离就是这个字母I。

抱歉回答有些冗长 - 我想解释一下这个算法，可以保证：@OmnipotentEntity是对的 - 在向你解释之后，我甚至更好地理解了它 :)

- Jacek Serafinski

---

你能发一份伪代码或者类似的东西吗？我觉得我已经理解了，但是看一下伪代码会更好。 - voidMainReturn

Answer 4

全文链接：http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/

首先，让我们仔细观察回文字符串，以找到一些有趣的属性。例如，S1 =“abaaba”和S2 =“abcba”，都是回文字符串，但它们之间的区别（即非长度或字符方面）是什么？ S1是一个以i = 2和i = 3之间的无形空格为中心的回文字符串（不存在的空格！）。另一方面，S2以i = 2处的字符（即c）为中心。为了优雅地处理回文字符串的中心，无论其长度为奇数还是偶数，我们通过在字符之间插入特殊字符$来转换回文字符串。然后，S1 =“abba”和S2 =“abcba”将转换为T1 =“$ a $ b $ a $ a $ b $ a $”（以i = 6为中心），T2 =“$ a $ b $ c $ b $ a $”（以i = 5为中心）。现在，我们可以看到中心存在且长度一致2 * n + 1，其中n =原始字符串的长度。例如，

                    i'          c           i           
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
   T1=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------

接下来，观察（转换后的）回文字符串T关于中心c的对称性，从而得到T [c-k] = T [c + k]，其中0 <= k <= c。也就是说，位置c-k和c+k相互镜像。换句话说，在中心c右侧的索引i上，镜像索引i'位于在c左侧，以使c-i'=i-c => i'=2*c-i，反之亦然。也就是说：

对于回文子字符串中心c右侧的每个位置i，其镜像位置为i'=2*c-i，反之亦然。

让我们定义一个数组P [0..2 * n]，使得P [i]等于以i为中心的回文字���串的长度。请注意，实际上，长度是通过忽略特殊字符$在原始字符串中的字符数来测量的。还让min和max分别是以c为中心的回文子字符串的最左边和最右边的边界。因此，min=c-P[c]，max=c+P[c]。例如，对于回文字符串S =“abaaba”，转换后的回文字符串T，镜像中心c = 6，长度数组P [0..12]，min=c-P[c]=6-6=0，max=c+P[c]=6+6=12，并且在以下图中显示了两个样本镜像索引i和i'。

      min           i'          c           i           max
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
    T=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
      -----------------------------------------------------

有了长度为P的数组，我们可以通过查看P中的最大元素来找到最长回文子串的长度。那就是说,

P[i]是以i为中心的转换后字符串T中回文子串的长度，在原始字符串S中则是以i/2为中心；因此最长回文子串将是从索引(i_max-P[i_max])/2开始的长度为P[i_max]的子串，其中i_max是P中最大元素的索引。

让我们在下面的非回文示例字符串S="babaabca"上绘制类似的图形。

                       min              c               max
                       |----------------|-----------------|
      --------------------------------------------------------------------
 idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
      --------------------------------------------------------------------- 
    T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
      ---------------------------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
      ---------------------------------------------------------------------

问题是如何高效地计算P。对称性表明，我们可以使用左侧镜像索引i'上先前计算的P[i']来计算P[i]的以下情况，从而跳过许多计算。假设我们有一个参考回文（第一个回文）来开始。

第三个中心位于第一个回文串右侧的回文串长度与以镜像中心位于左侧的第二个回文串的长度相同，如果第二个回文串至少比第一个回文串多一个字符。例如，在下面的图中，第一个回文串以c=8为中心，边界为min=4和max=12，第三个回文串以i=9为中心（镜像索引为i'=2*c-i=7），则P[i]=P[i']=1。这是因为第二个回文串以i'为中心完全包含在第一个回文串内。同样，P[10]=P[6]=0。

现在问题是如何检查这种情况？注意，由于对称性质，段[min..i']的长度等于段[i..max]的长度。还要注意的是，当第二个回文串完全包含在第一个回文串中时，第二个回文串的左边缘在第一个回文串的左边界min内。也就是说，

i'-P[i'] >= min => P[i']-i' < -min（否定） => P[i'] < i'-min => P[i'] < max-i（由于对称性质，max-i = i'-min）。

将所有情况合并为case 1：

P[i] = P[i']，当且仅当(max-i)>P[i']

如果第二个回文串遇到或超出第一个回文串的左边界，则第三个回文串保证至少具有从其自身中心到第一个回文串右侧最外字符的长度。该长度与第二个回文串中心到第一个回文串左边最外字符的长度相同。

例如，在下面的图中，第二个以i=5为中心的回文串超出了第一个回文串的左边界。因此，在这种情况下，无法说P[i]=P[i']。但是，以i=11为中心的第三个回文串的长度至少为其自身中心i到c为中心的第一个回文串的右边界max的长度。也就是说，P[i] >= 1。这意味着当且仅当超过max的下一个立即字符与镜像字符完全匹配时，第三个回文串可以扩展到max之外，并继续进行检查。例如，在这种情况下，P[13]!= P[9]，无法扩展。因此，P[i]=1。

那么如何检查这种情况？这只是case 1中失败的检查。也就是说，如果第二个回文串向左延伸超出第一个回文串的左边缘，则：

i'-P[i'] < min => P[i']-i' >= -min（否定） => P[i'] >= i'-min => P[i'] >= max-i（由于对称性质，max-i = i'-min）

换句话说，当(max-i)=min(P[i'], max-i)时，P[i]至少为(max-i)。如果第三个回文串确实扩展到max之外，则需要更新新回文串的中心和边界。

当以i为中心的回文串扩展超出max时，我们有一个新的（扩展的）回文串，因此有一个新的中心在c=i处。将max更新为新回文串的右侧边界。

合并所有情况后，可以得出非常美丽的公式：

Case 1：当且仅当(max-i)>P[i']时，P[i]=P[i'] Case 2：当(max-i)=min(P[i'], max-i)时，P[i]>=（max-i）。也就是说，当第三个回文串无法扩展到max之外时，P[i]=min(P[i'], max-i)。否则，我们在c=i的镜像字符与超过max

参考资料： 维基百科页面中的算法描述

- user3674869

---

你的证明混淆了不等式和严格不等式。 - Abhijit Sarkar

Answer 5

这篇材料对我理解很有帮助： http://solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html 定义T为以每个字符为中心的最长回文子串长度。

关键是，当较小的回文完全嵌入更长的回文中时，T[i]也应在更长的回文中对称。

否则，我们将不得不从头计算T[i]，而不是从对称的左侧部分归纳。

- Lin Jian

Answer 6

class Palindrome
{
    private int center;
    private int radius;

    public Palindrome(int center, int radius)
    {
        if (radius < 0 || radius > center)
            throw new Exception("Invalid palindrome.");

        this.center = center;
        this.radius = radius;
    }

    public int GetMirror(int index)
    {
        int i = 2 * center - index;

        if (i < 0)
            return 0;

        return i;
    }

    public int GetCenter()
    {
        return center;
    }

    public int GetLength()
    {
        return 2 * radius;
    }

    public int GetRight()
    {
        return center + radius;
    }

    public int GetLeft()
    {
        return center - radius;
    }

    public void Expand()
    {
        ++radius;
    }

    public bool LargerThan(Palindrome other)
    {
        if (other == null)
            return false;

        return (radius > other.radius);
    }

}

private static string GetFormatted(string original)
{
    if (original == null)
        return null;
    else if (original.Length == 0)
        return "";

    StringBuilder builder = new StringBuilder("#");
    foreach (char c in original)
    {
        builder.Append(c);
        builder.Append('#');
    }

    return builder.ToString();
}

private static string GetUnFormatted(string formatted)
{
    if (formatted == null)
        return null;
    else if (formatted.Length == 0)
        return "";

    StringBuilder builder = new StringBuilder();
    foreach (char c in formatted)
    {
        if (c != '#')
            builder.Append(c);
    }

    return builder.ToString();
}

public static string FindLargestPalindrome(string str)
{
    string formatted = GetFormatted(str);

    if (formatted == null || formatted.Length == 0)
        return formatted;

    int[] radius = new int[formatted.Length];

    try
    {
        Palindrome current = new Palindrome(0, 0);
        for (int i = 0; i < formatted.Length; ++i)
        {
            radius[i] = (current.GetRight() > i) ?
                Math.Min(current.GetRight() - i, radius[current.GetMirror(i)]) : 0;

            current = new Palindrome(i, radius[i]);

            while (current.GetLeft() - 1 >= 0 && current.GetRight() + 1 < formatted.Length &&
                formatted[current.GetLeft() - 1] == formatted[current.GetRight() + 1])
            {
                current.Expand();
                ++radius[i];
            }
        }

        Palindrome largest = new Palindrome(0, 0);
        for (int i = 0; i < radius.Length; ++i)
        {
            current = new Palindrome(i, radius[i]);
            if (current.LargerThan(largest))
                largest = current;
        }

        return GetUnFormatted(formatted.Substring(largest.GetLeft(), largest.GetLength()));
    }
    catch (Exception ex) 
    {
        Console.WriteLine(ex);
    }

    return null;
}

- Gevorg Meliksetyan

Answer 7

在JavaScript中快速查找字符串中最长回文的解决方案：

const lpal = str => {
  let lpal = ""; // to store longest palindrome encountered
  let pal = ""; // to store new palindromes found
  let left; // to iterate through left side indices of the character considered to be center of palindrome
  let right; // to iterate through left side indices of the character considered to be center of palindrome
  let j; // to iterate through all characters and considering each to be center of palindrome
  for (let i=0; i<str.length; i++) { // run through all characters considering them center of palindrome
    pal = str[i]; // initializing current palindrome
    j = i; // setting j as index at the center of palindorme
    left = j-1; // taking left index of j
    right = j+1; // taking right index of j
    while (left >= 0 && right < str.length) { // while left and right indices exist
      if(str[left] === str[right]) { //
        pal = str[left] + pal + str[right];
      } else {
        break;
      }
      left--;
      right++;
    }
    if(pal.length > lpal.length) {
      lpal = pal;
    }
    pal = str[i];
    j = i;
    left = j-1;
    right = j+1;
    if(str[j] === str[right]) {
      pal = pal + str[right];
      right++;
      while (left >= 0 && right < str.length) {
        if(str[left] === str[right]) {
          pal = str[left] + pal + str[right];
        } else {
          break;
        }
        left--;
        right++;
      }
      if(pal.length > lpal.length) {
        lpal = pal;
      }
    }
  }
  return lpal;
}

示例输入

console.log(lpal("gerngehgbrgregbeuhgurhuygbhsbjsrhfesasdfffdsajkjsrngkjbsrjgrsbjvhbvhbvhsbrfhrsbfsuhbvsuhbvhvbksbrkvkjb"));

输出

asdfffdsa

- user6184932

Answer 8

我也曾经遇到过同样的挫折和困难，但是我在这个页面https://www.hackerearth.com/practice/algorithms/string-algorithm/manachars-algorithm/tutorial/上找到了最容易理解的解决方案。 我尝试用自己的方式实现这个解决方案，现在我认为我已经理解了这个算法。我还尽可能地在代码中添加了许多解释来解释算法。希望这能帮到你！

#Manacher's Algorithm
def longestPalindrome(s):
  s = s.lower()
  #Insert special characters, #, between characters
  #Insert another special in the front, $, and at the end, @, of string  to avoid bound checking.
  s1 = '$#'
  for c in s:
      s1 += c + '#'
  s1 = s1+'@'
  #print(s, " -modified into- ", s1)

  #Palin[i] = length of longest palindrome start at center i
  Palin = [0]*len(s1)

  #THE HARD PART: THE MEAT of the ALGO

  #c and r help keeping track of the expanded regions.
  c = r = 0

  for i in range(1,len(s1)-1): #NOTE: this algo always expands around center i

      #if we already expanded past i, we can retrieve partial info 
      #about this location i, by looking at the mirror from left side of center.

      if r > i:  #---nice, we look into memory of the past---
          #look up mirror from left of center c
          mirror = c - (i-c)

          #mirror's largest palindrome = Palin[mirror]

          #case1: if mirror's largest palindrome expands past r, choose r-i
          #case2: if mirror's largest palindrome is contains within r, choose Palin[mirror]
          Palin[i] = min(r-i, Palin[mirror]) 

      #keep expanding around center i
      #NOTE: instead of starting to expand from i-1 and i+1, which is repeated work
      #we start expanding from Palin[i], 
      ##which is, if applicable, updated in previous step
      while s1[i+1+Palin[i]] == s1[i-1-Palin[i]]:
          Palin[i] += 1

      #if expanded past r, update r and c
      if i+Palin[i] > r:
          c = i
          r = i + Palin[i]

  #the easy part: find the max length, remove special characters, and return
  max_center = max_length = 0
  for i in range(len(s1)):
      if Palin[i] > max_length:
          max_length = Palin[i]
          max_center = i  
  output = s1[max_center-max_length : max_center+max_length]
  output = ''.join(output.split('#'))
  return output # for the (the result substring)

- nah

Answer 9

using namespace std;

class Palindrome{
public:
    Palindrome(string st){
        s = st; 
        longest = 0; 
        maxDist = 0;
        //ascii: 126(~) - 32 (space) = 94 
        // for 'a' to 'z': vector<vector<int>> v(26,vector<int>(0)); 
        vector<vector<int>> v(94,vector<int>(0)); //all ascii 
        mDist.clear();
        vPos = v; 
        bDebug = true;
    };

    string s;
    string sPrev;    //previous char
    int longest;     //longest palindrome size
    string sLongest; //longest palindrome found so far
    int maxDist;     //max distance been checked 
    bool bDebug;

    void findLongestPal();
    int checkIfAnchor(int iChar, int &i);
    void checkDist(int iChar, int i);

    //store char positions in s pos[0] : 'a'... pos[25] : 'z' 
    //       0123456
    // i.e. "axzebca" vPos[0][0]=0  (1st. position of 'a'), vPos[0][1]=6 (2nd pos. of 'a'), 
    //                vPos[25][0]=2 (1st. pos. of 'z').  
    vector<vector<int>> vPos;

    //<anchor,distance to check> 
    //   i.e.  abccba  anchor = 3: position of 2nd 'c', dist = 3 
    //   looking if next char has a dist. of 3 from previous one 
    //   i.e.  abcxcba anchor = 4: position of 2nd 'c', dist = 4 
    map<int,int> mDist;
};

//check if current char can be an anchor, if so return next distance to check (3 or 4)
// i.e. "abcdc" 2nd 'c' is anchor for sub-palindrome "cdc" distance = 4 if next char is 'b'
//      "abcdd: 2nd 'd' is anchor for sub-palindrome "dd"  distance = 3 if next char is 'c'
int Palindrome::checkIfAnchor(int iChar, int &i){
    if (bDebug)
          cout<<"checkIfAnchor. i:"<<i<<" iChar:"<<iChar<<endl;
    int n = s.size();
    int iDist = 3;
    int iSize = vPos[iChar].size();
    //if empty or distance to closest same char > 2
    if ( iSize == 0 || vPos[iChar][iSize - 1] < (i - 2)){
        if (bDebug)
              cout<<"       .This cannot be an anchor! i:"<<i<<" : iChar:"<<iChar<<endl; 
        //store char position
        vPos[iChar].push_back(i);
        return -1; 
    }

    //store char position of anchor for case "cdc"
    vPos[iChar].push_back(i);    
    if (vPos[iChar][iSize - 1] == (i - 2))
        iDist = 4;
    //for case "dd" check if there are more repeated chars
    else {
        int iRepeated = 0;
        while ((i+1) < n && s[i+1] == s[i]){
            i++;
            iRepeated++;
            iDist++; 
            //store char position
            vPos[iChar].push_back(i);
        }
    }

    if (bDebug)
          cout<<"       .iDist:"<<iDist<<" i:"<<i<<endl; 

    return iDist;
};

//check distance from previous same char, and update sLongest
void Palindrome::checkDist(int iChar, int i){
    if (bDebug)
            cout<<"CheckDist. i:"<<i<<" iChar:"<<iChar<<endl;
    int iDist;
    int iSize = vPos[iChar].size();
    bool b1stOrLastCharInString; 
    bool bDiffDist;

    //checkAnchor will add this char position 
    if ( iSize == 0){
        if (bDebug)
            cout<<"       .1st time we see this char. Assign it INT_MAX Dist"<<endl; 
        iDist = INT_MAX;
    }
    else {
        iDist = i - vPos[iChar][iSize - 1]; 
    }

    //check for distances being check, update them if found or calculate lengths if not.
    if (mDist.size() == 0) {
        if (bDebug)
             cout<<"       .no distances to check are registered, yet"<<endl;
        return;
    }

    int i2ndMaxDist = 0;
    for(auto it = mDist.begin(); it != mDist.end();){
        if (bDebug)
                cout<<"       .mDist. anchor:"<<it->first<<" . dist:"<<it->second<<endl; 
        b1stOrLastCharInString = false; 
        bDiffDist = it->second == iDist;  //check here, because it can be updated in 1st. if
        if (bDiffDist){
            if (bDebug)
                cout<<"       .Distance checked! :"<<iDist<<endl;
            //check if it's the first char in the string
            if (vPos[iChar][iSize - 1] == 0 || i == (s.size() - 1))
                b1stOrLastCharInString = true;
            //we will continue checking for more...
            else {
                it->second += 2; //update next distance to check
                if (it->second > maxDist) {
                     if (bDebug)
                          cout<<"       .previous MaxDist:"<<maxDist<<endl;
                     maxDist = it->second;
                     if (bDebug)
                          cout<<"       .new MaxDist:"<<maxDist<<endl;
                }
                else if (it->second > i2ndMaxDist) {//check this...hmtest
                     i2ndMaxDist = it->second;
                     if (bDebug)
                          cout<<"       .second MaxDist:"<<i2ndMaxDist<<endl;
                }
                it++; 
            }
        }
        if (!bDiffDist || b1stOrLastCharInString) {
            if (bDebug && it->second != iDist)
                cout<<"       .Dist diff. Anchor:"<<it->first<<" dist:"<<it->second<<" iDist:"<<iDist<<endl;
            else if (bDebug) 
                cout<<"       .Palindrome found at the beggining or end of the string"<<endl;

            //if we find a closest same char.
            if (!b1stOrLastCharInString && it->second > iDist){
                if (iSize > 1) {
                   if (bDebug)
                       cout<<"       . < Dist . looking further..."<<endl; 
                   iSize--;  
                   iDist = i - vPos[iChar][iSize - 1];
                   continue;    
                }
            }
            if (iDist == maxDist) {
                maxDist = 0;
                if (bDebug)
                     cout<<"       .Diff. clearing Max Dist"<<endl;
            }
            else if (iDist == i2ndMaxDist) {
                i2ndMaxDist = 0;
                if (bDebug)
                      cout<<"       .clearing 2nd Max Dist"<<endl; 
            }

            int iStart; 
            int iCurrLength;
            //first char in string
            if ( b1stOrLastCharInString && vPos[iChar].size() > 0 && vPos[iChar][iSize - 1] == 0){
                iStart = 0;
                iCurrLength = i+1;
            }
            //last char in string
            else if (b1stOrLastCharInString && i == (s.size() - 1)){
                iStart = i - it->second; 
                iCurrLength = it->second + 1;
            }
            else {
                iStart = i - it->second + 1; 
                iCurrLength = it->second - 1;  //"xabay" anchor:2nd. 'a'. Dist from 'y' to 'x':4. length 'aba':3
            }

            if (iCurrLength > longest){
                if (bDebug)
                      cout<<"       .previous Longest!:"<<sLongest<<" length:"<<longest<<endl;
                longest = iCurrLength;               
                sLongest = s.substr(iStart, iCurrLength);

                if (bDebug)
                      cout<<"       .new Longest!:"<<sLongest<<" length:"<<longest<<endl;
            }

            if (bDebug)
                  cout<<"       .deleting iterator for anchor:"<<it->first<<" dist:"<<it->second<<endl; 

            mDist.erase(it++);
        }
    }


    //check if we need to get new max distance
    if (maxDist == 0 && mDist.size() > 0){ 
        if (bDebug)
              cout<<"       .new maxDist needed";
        if (i2ndMaxDist > 0) {
            maxDist = i2ndMaxDist;
            if (bDebug)
              cout<<"       .assigned 2nd. max Dist to max Dist"<<endl;
        }
        else {
            for(auto it = mDist.begin(); it != mDist.end(); it++){
                if (it->second > maxDist)
                    maxDist = it->second;
            }
            if (bDebug)
              cout<<"       .new max dist assigned:"<<maxDist<<endl;
        }
    }  
};        

void Palindrome::findLongestPal(){
    int n = s.length(); 
    if (bDebug){
        cout<<"01234567891123456789212345"<<endl<<"abcdefghijklmnopqrstuvwxyz"<<endl<<endl;            
        for (int i = 0; i < n;i++){
            if (i%10 == 0)
                cout<<i/10;
            else
                cout<<i;
        }
        cout<<endl<<s<<endl;
    }
    if (n == 0)
        return;

    //process 1st char
    int j = 0;
    //for 'a' to 'z' : while (j < n && (s[j] < 'a' && s[j] > 'z'))
    while (j < n && (s[j] < ' ' && s[j] > '~'))
        j++;
    if (j > 0){
        s.substr(j);
        n = s.length();
    }
    // for 'a' to 'z' change size of vector from 94 to 26 : int iChar = s[0] - 'a';
    int iChar = s[0] - ' ';
    //store char position
    vPos[iChar].push_back(0);  

    for (int i = 1; i < n; i++){
        if (bDebug)
            cout<<"findLongestPal. i:"<<i<<" "<<s.substr(0,i+1)<<endl; 
        //if max. possible palindrome would be smaller or equal 
        //             than largest palindrome found then exit
        //   (n - i) = string length to check 
        //   maxDist: max distance to check from i 
        int iPossibleLongestSize = maxDist + (2 * (n - i));
        if ( iPossibleLongestSize <= longest){
            if (bDebug)
                cout<<"       .PosSize:"<<iPossibleLongestSize<<" longest found:"<<iPossibleLongestSize<<endl;
            return;
        }

        //for 'a' to 'z' : int iChar = s[i] - 'a';
        int iChar = s[i] - ' ';
        //for 'a' to 'z': if (iChar < 0 || iChar > 25){
        if (iChar < 0 || iChar > 94){
            if (bDebug)
                cout<<"       . i:"<<i<<" iChar:"<<s[i]<<" skipped!"<<endl;
            continue;
        }

        //check distance to previous char, if exist
        checkDist(iChar, i);

        //check if this can be an anchor
        int iDist = checkIfAnchor(iChar,i);
        if (iDist == -1) 
            continue;

        //append distance to check for next char.
        if (bDebug)
                cout<<"       . Adding anchor for i:"<<i<<" dist:"<<iDist<<endl;
        mDist.insert(make_pair(i,iDist));

        //check if this is the only palindrome, at the end
        //i.e. "......baa" or "....baca" 
        if (i == (s.length() - 1) && s.length() > (iDist - 2)){
            //if this is the longest palindrome! 
            if (longest < (iDist - 1)){
                sLongest = s.substr((i - iDist + 2),(iDist - 1));
            }
        }
    }
};

int main(){
    string s;
    cin >> s;

    Palindrome p(s);
    p.findLongestPal();
    cout<<p.sLongest; 
    return 0;
}

- ektormelendez

---

你好，欢迎来到Stack Overflow！看起来你在这个答案上花了不少时间，但是像这样的大块代码很难作为回答问题的方式理解。请查看答案格式选项，并尝试将代码分成重要部分的解释而不是代码注释，或者在你的答案中加入一些解释以帮助理解。 - Carl Poole

此外，虽然答案总是受到欢迎的，但这个问题已经在4年前被提出，并且已经有了一个被接受的解决方案。请尽量避免通过回答问题来“顶”它们，除非该问题尚未标记为已解决，或者您找到了一个明显更好的解决问题的方法 :) - Obsidian Age