72

在花了大约 6-8 小时试图消化 Manacher 的算法之后，我准备认输。但在我这样做之前，这是黑暗中的最后一枪：谁能解释一下？我不关心代码。我希望有人解释算法。

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

我理解你为什么要转换字符串，比如 'abba' 到 #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'] = 7 并且 P[i] 不小于或等于 R - i 时 P[i] 等于 5。

如果您不熟悉该算法，这里还有一些链接：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)。

4

10 回答 10

39

我同意链接的解释中的逻辑不太正确。我在下面给出一些细节。

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']，但我认为它应该大于或等于 Ri，并且解释支持了这一点。

由于 P[i'] 大于 Ri，以 i' 为中心的回文延伸超过以 C 为中心的回文。我们知道以 i 为中心的回文将至少是 Ri 字符宽，因为我们仍然具有对称性，但我们必须明确搜索。

如果 P[i'] 不大于 Ri，那么以 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']<=Ri。由于我们距离以 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'] < Ri，那么我们知道 P[i]==P[i']，因为我们仍在以 C 为中心的回文串内。

如果 P[i'] > Ri，那么我们知道 P[i]==Ri，否则以 C 为中心的回文将延伸超过 R。

所以展开式实际上只在 P[i']==Ri 的特殊情况下是必要的，所以我们不知道 P[i] 处的回文是否可能更长。

这在实际代码中通过设置 P[i]=min(P[i'],Ri) 然后总是扩展来处理。这种方法不会增加时间复杂度，因为如果不需要扩展，则进行扩展所花费的时间是恒定的。

于 2012-05-06T06:49:57.120 回答
13

到目前为止，我在以下链接中找到了最好的解释之一：

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

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

除了这个链接，我还找到了代码

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

我希望它对其他努力理解这个算法的症结的人有所帮助。

于 2013-12-24T19:52:39.283 回答
12

这个网站上的算法在某种程度上似乎是可以理解的 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 的左侧复制到 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 更改为包含回文的内容。什么？OOOOOh - 这就是诀窍。中心在我们当前回文的右侧的更大回文的唯一可能性是它已经在回文的右侧（和左侧）。

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

哇咔咔

如前所述 - 让最后一个我成为比 KIKEEKIK 更大的苍白球的中心：

WOWIKIKEEKIKEEKIKIW

让我们将数组组成我们的旧 pallindrom 并找出如何处理附加信息。

为了

[_ 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 - a 3rd 将是最长的回文，但让我们暂时忘记它。让我们将数组中的数字从 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 个空格移到 3 的右侧 - 您将超出数组。这意味着它可以是最大的回文线的中间，而你可以跳得最远的是这个字母 I。

对不起这个答案的长度 - 我想解释一下算法并可以向你保证 - @OmnipotentEntity 是对的 - 在向你解释后我理解得更好:)

于 2013-02-18T00:43:46.427 回答
5

全文：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" 将被转换为以 i=6 和 T2="$a$b$c$b 为中心的 T1="$a$b$a$a$b$a$" $a$" 以 i=5 为中心。现在，我们可以看到中心是存在的，长度是一致的 2*n+1，其中 n = 原始字符串的长度。例如，

                    我是           
      -------------------------------------------------- ---
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      -------------------------------------------------- ---
   T1=| $ | 一个 | $ | 乙 | $ | 一个 | $ | 一个 | $ | 乙 | $ | 一个 | $ |
      -------------------------------------------------- ---

接下来，从围绕中心 c 的（变换的）回文 T 的对称性质观察，对于 0<= k<= c，T[ck] = T[c+k]。即位置 ck 和 c+k 相互镜像。换一种说法，对于中心 c 右侧的索引 i，镜像索引 i' 在 c 的左侧，这样 ci'=ic => i'=2*ci 反之亦然。那是，

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

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

      min i' ci max
      -------------------------------------------------- ---
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      -------------------------------------------------- ---
    T=| $ | 一个 | $ | 乙 | $ | 一个 | $ | 一个 | $ | 乙 | $ | 一个 | $ |
      -------------------------------------------------- ---
    P=| 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
      -------------------------------------------------- ---

有了这样一个长度数组 P，我们可以通过查看 P 的最大元素来找到最长回文子串的长度。也就是说，

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

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

                       最小 c 最大
                       |----------------|-----------------|
      -------------------------------------------------- ------------------
 idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
      -------------------------------------------------- ------------------
    T=| $ | 乙 | $ | 一个 | $ | 乙 | $ | 一个 | $ | 一个 | $ | 乙 | $ | c | $ | 一个 | $ |
      -------------------------------------------------- ------------------
    P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
      -------------------------------------------------- ------------------

问题是如何有效地计算 P。对称属性暗示了以下情况，我们可以通过在左侧的镜像索引 i' 处使用先前计算的 P[i'] 来计算 P[i]，从而跳过大量计算。假设我们有一个参考回文（第一个回文）开始。

  1. 如果第二个回文位于第一个回文的边界内，则其中心位于第一个回文右侧的第三个回文的长度将与锚定在左侧镜像中心的第二个回文的长度完全相同。至少一个字符。
    例如在下图中，第一个回文以 c=8 为中心，以 min=4 和 max=12 为边界，以 i=9 为中心的第三个回文的长度（镜像索引 i'= 2*ci = 7）为, P[i] = P[i'] = 1。这是因为以 i' 为中心的第二个回文位于第一个回文的范围内。同样，P[10] = P[6] = 0。 
    
                                      |----第三----|
                              |----第二----|        
                       |-----------第一回文---------|
                       min i' ci max
                       |------------|---|---|-------------|
      -------------------------------------------------- ------------------
 idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
      -------------------------------------------------- ------------------
    T=| $ | 乙 | $ | 一个 | $ | 乙 | $ | 一个 | $ | 一个 | $ | 乙 | $ | c | $ | 一个 | $ |
      -------------------------------------------------- ------------------
    P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | ? | ? | ? | ? | ? | ? | ? | ? |
      -------------------------------------------------- ------------------
    现在，问题是如何检查这种情况？请注意，由于线段 [min..i'] 的对称属性长度等于线段 [i..max] 的长度。另外，请注意，如果第 2 个回文的左边缘在第 1 个回文的左边界内，则第 2 个回文完全在第一个回文内。那是， 
            i'-P[i'] >= min
        =>P[i']-i' < -min（否定）
        =>P[i'] < i'-min
        =>P[i'] < max-i [(max-i)=(i'-min) 由于对称属性]。
    结合案例1中的所有事实，
    P[i] = P[i'], iff (max-i) > P[i']
  2. 如果第二个回文符合或超出第一个回文的左边界，则保证第三个回文至少具有从它自己的中心到第一个回文的最右外字符的长度。从第二个回文的中心到第一个回文的最左边的字符，这个长度是相同的。
    例如在下图中，以 i=5 为中心的第二个回文数超出了第一个回文数的左边界。所以，在这种情况下，我们不能说 P[i]=P[i']。但是以 i=11 为中心的第三个回文的长度，P[i] 至少是从其中心 i=11 到以 c 为中心的第一个回文的右边界 max=12 的长度。也就是说，P[i]>=1。这意味着当且仅当超过 max 的下一个直接字符与镜像字符完全匹配时，第三个回文可以扩展到超过 max，并且我们继续这个检查。例如，在这种情况下 P[13]!=P[9] 并且它不能被扩展。所以，P[i] = 1。 
                                                        
              |-------第二回文-----| |----第三----|---？    
                       |-----------第一回文---------|
                       min i' ci max
                       |----|------------|------------|------|
      -------------------------------------------------- ------------------
 idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
      -------------------------------------------------- ------------------
    T=| $ | 乙 | $ | 一个 | $ | 乙 | $ | 一个 | $ | 一个 | $ | 乙 | $ | c | $ | 一个 | $ |
      -------------------------------------------------- ------------------
    P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | ? | ? | ? | ? | ? | ? |
      -------------------------------------------------- ------------------
    那么，如何检查这种情况呢？这只是案例 1 的失败检查。也就是说，第二个回文将延伸超过第一个回文的左边缘当且仅当， 
            i'-P[i'] < 分钟
        =>P[i']-i' >= -min [否定]
        =>P[i'] >= i'-min
        =>P[i'] >= max-i [(max-i)=(i'-min) 由于对称属性]。
    也就是说，P[i] 至少是 (max-i) iff (max-i) P[i]>=(max-i), iff (max-i) 现在，如果第三个回文确实超出了 max，那么我们需要更新新回文的中心和边界。
    如果以 i 为中心的回文确实扩展到超过最大值，那么我们有新的（扩展的）回文，因此在 c=i 处有一个新的中心。将 max 更新到新回文的最右边边界。
    结合案例 1 和案例 2 中的所有事实，我们可以得出一个非常漂亮的小公式： 
            案例一：P[i] = P[i'], iff (max-i) > P[i']
        情况 2：P[i]>=(max-i), iff (max-i) = min(P[i'], max-i)。
    也就是说，当第三个回文数不可扩展超过 max 时，P[i]=min(P[i'], max-i)。否则，我们在 c=i 和新的 max=i+P[i] 的中心有新的第三回文数。
  3. 第一回文和第二回文都没有提供信息来帮助确定第四回文的回文长度，第四回文的中心在第一回文的右侧之外。
    也就是说，如果 i>max，我们不能先发制人地确定 P[i]。那是，
    P[i] = 0，当且仅当 max-i < 0
    结合所有情况，我们得出公式：
    P[i] = 最大值>i ? min(P[i'], max-i) : 0. 如果我们可以扩展超出 max，那么我们通过将超出 max 的字符与相对于 c=i 处的新中心的镜像字符匹配来扩展。最后，当我们有不匹配时，我们更新新的 max=i+P[i]。

参考：wiki页面中的算法描述

于 2014-08-04T16:05:42.493 回答
1

我使用动画图形制作了有关此算法的视频。希望它能帮助你理解它！ https://www.youtube.com/watch?v=kbUiR5YWUpQ

于 2017-01-26T13:31:40.677 回答
1

该材料对我理解它有很大帮助：http: //solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html

将 T 定义为以每个字符为中心的最长回文子串的长度。

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

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

于 2017-06-09T08:20:50.787 回答
0 
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;
}
于 2013-09-30T06:37:21.063 回答
0

在字符串中查找最长回文的快速 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
于 2019-08-23T01:58:29.480 回答
0

我经历了同样的挫折/挣扎，并在此页面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)
于 2019-12-22T00:03:57.170 回答
-1 
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;
}
于 2017-02-28T20:20:08.273 回答