Manacher 算法(在线性时间内寻找最长回文子串的算法)

在花了6-8个小时试图消化教练的算法之后，我准备放弃了。但在此之前，我还有最后一个问题: 有人能解释一下吗？我不在乎密码。我需要有人解释一下 算法。

这似乎是其他人在解释算法时喜欢的一个地方: 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)。

40903 次浏览
小开
最佳答案

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

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)来处理这个问题，然后总是展开。这种方法不会增加时间的复杂性，因为如果不需要展开，展开所需的时间是恒定的。

小开

在这个网站上的算法似乎可以理解的某一点 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,0,1,0,1,8]

为了

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

诀窍在于你已经知道8后面的7个(8-1)数字很可能和左边的数字一样，所以下一步就是自动从8的左边复制7个数字到8的右边，记住它们还不是最终的。 数组应该是这样的

[0,1,0,3,0,1,0,1,0,1,0,1,0,1,8,1,0,1,0,1,0,1,0,1,0,1,0,0,3](我们在8)

为了

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

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

WOWILIKEEKIL-让我们尝试用 EKIL 中的某个中心来制作更大的回文。 但这是不可能的-我们需要改变单词 EKIL 的东西，包含回文。 什么? 这就是诀窍。 唯一的可能性是有一个更大的回文与中心在我们目前的回文的右边是，它已经在右边(和左边)的回文。

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

WOWIKIKEKIK

正如前面所说的——让最后一个我成为比 KIKEKIK 更大的回旋体的中心:

WOWIKIKEKEEKIKIW

让我们使数组到我们的旧 pallindrom，并找出如何利用额外的信息。

为了

[ W _ O _ W _ I _ K _ I _ K _ E _ K _ I _ K _ 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 3将是最长的回文，但让我们暂时忘记它。让我们将数组中的数字从8的左侧复制到右侧(8个数字)

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

在我们的循环中，我们处于 E 和8之间。我(未来最大回文中间)有什么特别之处是我们不能直接跳到 K (当前最大回文的最后一个字母) ？ 特别之处在于它超过了数组的当前大小... 怎么超过的？ 如果你将3个空格移动到3的右边-你就脱离了数组。这意味着它可以是最大的回文的中间，你能跳得最远的是这个字母 I。

对于这个答案的冗长，我很抱歉——我想解释一下这个算法，我可以向你保证——@OmnipotentEntity 是正确的——在向你解释之后，我对它的理解会更好:)

小开 
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;
}
小开

到目前为止，我在以下连结找到一个最好的解释:

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

它还提供了问题中提到的第一个链接中使用的同一个字符串示例(babcbabcbaccba)的可视化。

除了这个链接，我还在

Http://algs4.cs.princeton.edu/53substring/manacher.java.html

我希望这将有助于其他人努力了解这个算法的关键。

小开

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

First of all lets observe closely to a palindrome in order to find some interesting properties. For example, S1 = "abaaba" and S2="abcba", both are palindrome but what is the non-trivial (i.e. not length or characters) difference between them? S1 is a palindrome centered around the invisible space between i=2 and i=3 (non-existent space!). On the other hand S2 is centered around character at i=2 (ie. c). In order to graciously handle the center of a palindrome irrespective of the odd/even length, lets transform the palindrome by inserting special character $ in between characters. Then S1="abba" and S2="abcba" will be transformed into T1="$a$b$a$a$b$a$" centered at i=6 and T2="$a$b$c$b$a$" centered at i=5. Now, we can see that centers are existent and lengths are consistent 2*n+1, where n=length of original string. For example, 

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

接下来，观察一个(转换后的)回文对称属性在中心 c 周围的位置，对于0 < = k < = c，t [ c-k ] = T [ c + k ]。也就是说 c-k 和 c + k 的位置是彼此的镜像。换句话说，对于中心 c 右边的索引 i，镜像索引 i’在 c 的左边，这样 c-i’= i-c = > i’= 2 * c-i，反之亦然。就是,

对于回文子串中心 c 右侧的每个位置 i，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 的 max 元素来找到最长回文子串的长度。就是,

P [ i ]是回文子串的长度，在变换后的字符串 T 中以 i 为中心，即。因此最长回文子串是从 index (iMax-P [ iMax])/2开始的长度为 P [ iMax]的子字符串，这样 iMax就是 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 ] ，因此跳过了很多计算。让我们假设我们有一个引用回文(第一个回文)开始。

  1. 如果第二个回文在第一个回文的范围内，至少有一个字符，那么第三个回文的中心在第一个回文的右边，它的长度将与锚定在左边镜像中心的第二个回文的长度完全相同。
    例如，在下图中，第一个回文集中心为 c = 8，以 min = 4和 max = 12为界，第三个回文集中心为 i = 9(镜像索引 i’= 2 * c-i = 7)的长度为，P [ i ] = P [ i’] = 1。这是因为以 i’为中心的第二个回文在第一个回文的范围内。类似地，P [10] = P [6] = 0。 
    



|----3rd----|
|----2nd----|
|-----------1st Palindrome---------|
min          i'  c   i           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 | ? | ? | ? | ? | ? | ? | ? | ? |
---------------------------------------------------------------------
    Now, question is how to check this case? Note that, due to symmetric property length of segment [min..i'] is equals to the length of segment [i..max]. Also, note that 2nd palindrome is completely within 1st palindrome iff left edge of the 2nd palindrome is inside the left boundary, min of the 1st palindrome. That is, 
    

i'-P[i'] >= min
=>P[i']-i' < -min (negate)
=>P[i'] < i'-min
=>P[i'] < max-i [(max-i)=(i'-min) due to symmetric property].
    综合案例一的所有事实,
    P [ i ] = P [ i’] ，if (max-i) & gt 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. 
    |-------2nd palindrome------|   |----3rd----|---?
|-----------1st Palindrome---------|
min  i'          c           i   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的失败检查。也就是说，第二回文将延伸超过第一回文的左边缘, 
    

i'-P[i'] < min
=>P[i']-i' >= -min [negate]
=>P[i'] >= i'-min
=>P[i'] >= max-i [(max-i)=(i'-min) due to symmetric property].
    也就是说，P [ i ]至少是(max-i)如果(max-i) P [ i ] > = (max-i) ，如果(max-i) 现在，如果第三个回文超出了 max，那么我们需要更新新回文的中心和边界。
    如果以 i 为中心的回文扩展到 max 之后，那么我们就有了新的(扩展的)回文，因此在 c = i 处有一个新的中心，将 max 更新到新回文的最右边界。
    综合情况1和情况2的所有事实，我们可以得出一个非常漂亮的小公式: 
    

Case 1: P[i] = P[i'],  iff (max-i) > P[i']
Case 2: P[i]>=(max-i), iff (max-i) = min(P[i'], max-i).
    也就是说，P [ i ] = min (P [ i’] ，max-i) ，当第三个回文不可扩展超过 max 时。否则，我们有新的第三回文在中心 c = i 和新的 max = i + P [ i ]。
  3. 第一个和第二个回文都没有提供信息来帮助确定中心在第一个回文右边以外的第四个回文的回文长度。 也就是说，如果 i > max 我们不能预先确定 P [ i ],
    P [ i ] = 0，如果 max-i & lt
    综合所有的案例，我们得出公式:
    P [ i ] = max > i？Min (P [ i’] ，max-i) : 0。如果我们可以扩展超过最大值，那么我们通过匹配超过最大值的字符来扩展与镜像字符相关的 c = i 的新中心。最后，当我们有一个不匹配时，我们更新 new max = i + P [ i ]。

参考资料: 维基页面中的算法描述

小开 
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;
}
小开

这些材料对我理解它们很有帮助: Http://solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html

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

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

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

小开

查找字符串中最长回文的快速 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
小开

我经历了同样的挫折/挣扎，我在这个页面上找到了解决方案，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)

提交答案