Manacheralgorithm（在线性时间内find最长回文子串的algorithm）
花费大约6-8个小时来消化Manacher的algorithm，我准备投入毛巾。 但在此之前，这是黑暗中的最后一击：任何人都可以解释一下吗？ 我不在乎代码。 我想要有人解释algorithm 。
这似乎是其他人似乎喜欢解释algorithm的地方： http : //www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
我明白你为什么要把string，比如'abba'转换成＃a＃b＃b＃a＃之后，比我迷路了。 例如，前面提到的网站的作者说，algorithm的关键部分是：
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。
如果你不熟悉algorithm，这里有一些更多的链接： http : //tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html （我试过这一个，但术语是可怕的和混乱的，首先，有些东西没有定义，而且variables太多，你需要一个清单来回忆什么是variables。
另一个是： http : //www.akalin.cx/longest-palindrome-linear-time （祝你好运）
该algorithm的基本要点是在线性时间内find最长的回文。 它可以在O（n ^ 2）中以最小到中等的努力完成。 这个algorithm被认为是相当“聪明”的，把它降到O（n）。
我同意这个逻辑在链接的解释中是不太正确的。 我在下面提供一些细节。
Manacher的algorithm填入一张表P [i]，其中包含以i为中心的回文多远。 如果P [5] = 3，则位置5两边的三个字符是回文的一部分。 该algorithm利用了这样一个事实，即如果你发现了一个长的回文，你可以通过查看左边P的值来快速填写回文右边的P的值，因为它们大多数应该是相同。
我将首先解释你正在谈论的案例，然后根据需要扩展这个答案。
R表示以C为中心的回文右侧的索引。下面是你指定的地方的状态：
C=11 R=20 i=15 i'=7 P[i']=7 Ri=5
逻辑是这样的：
if P[i']<=Ri: // not true else: // P[i] is at least 5, but may be greater
链接中的伪代码表示如果testing失败，P [i]应该大于或等于P [i']，但是我认为它应该大于或等于Ri，并且解释支持那个。
由于P [i']大于Ri，以i'为中心的回文延伸经过以C为中心的回文。我们知道以i为中心的回文将至less有Ri个字符宽，因为我们仍然具有对称性，但是我们必须明确地search。
如果P [i']不大于Ri，那么以i'为中心的最大回文在以C为中心的最大回文内，所以我们知道P [i]不可能大于P [i “]。 如果是的话，我们会有矛盾的。 这意味着我们可以延伸以P [i']为中心的回文，但是如果可以的话，那么由于对称性，我们也可以延伸以i'为中心的回文，但它已经应该尽可能大。
前面说明了这种情况：
C=11 R=20 i=13 i'=9 P[i']=1 Ri=7
在这种情况下，P [i'] <= Ri。 由于我们距离以C为中心的回文边缘还有7个字符，所以我们知道我周围至less有7个字符与i'周围的7个字符相同。 由于我周围只有一个字母回文，所以我周围还有一个字母回文。
j_random_hacker注意到逻辑应该更像这样：
if P[i']<Ri then P[i]=P[i'] else if P[i']>Ri then P[i]=Ri else P[i]=Ri + 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）在实际代码中处理的，然后始终展开。 这样做并不会增加时间复杂性，因为如果不需要扩展，扩展所需的时间是不变的。
这个网站上的algorithm似乎可以理解的某些点http://www.akalin.cx/longest-palindrome-linear-time
要理解这个特定的方法，最好的办法是试着解决纸上的问题，并抓住你可以实现的技巧，以避免检查每个可能中心的回文。
首先回答自己 – 当你find一个给定长度的回文，让我们说5 – 你不能跳下回文结束（跳过4个字母和4个中间字母）吗？
如果您尝试创build一个长度为8的回文，并将另一个长度大于8的回文放置在第一个回文的右侧，您会发现一些有趣的事情。 尝试一下：回文长度为8 – WOWILIKEEKIL – Like + ekiL = 8现在在大多数情况下，你可以写下两个E之间的距离作为中心，数字8作为长度，跳到最后一个L之后寻找大回文的中心。
这种方法是不正确的，大回文的中心可以在ekiL里面，如果你在最后一个L之后跳，你会错过它。
findLIKE + EKIL之后，在这些algorithm使用的数组中放置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之后的下一个8（8-1）数字很可能与左侧相同，所以下一步就是自动从左边的8到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]
举个例子，这样的跳跃会破坏我们目前的解决scheme，看看我们能注意到什么。
WOWILIKEEKIL – 让我们尝试在EKIL内部的中心做更大的回文。 但它不可能 – 我们需要将EKIL改为包含回文的东西。 什么？ OOOOOh – 这就是诀窍。 唯一可能的方法是在我们目前的回文的右边有一个更大的回文，它已经在回文的右边（左边）。
让我们试着build立一个基于WOWILIKEEKIL我们需要改变EKIL为例如EKIK与我作为一个更大的回文中心 – 记得改变喜欢KIKE以及。 我们棘手的回文的第一个字母将是：
WOWIKIKEEKIK
如前所述 – 让我最后一个比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
我们知道下一个我将会是最长的一个，但是让我们忘了一下吧。 让我们从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]
在我们的循环中，我们处于E和8之间。对于我（我们最大的pallindrome的未来中间），我们不能跳到K（当前最大的pallindrome的最后一个字母）的特别之处是什么？ 特别的是，它超出了arrays的当前大小…怎么样？ 如果你在3的右边移动3个空格 – 你已经失去arrays了。 这意味着它可能是最大的悲剧的中间，你可以跳得最远的是这封信。
对不起，这个答案的长度 – 我想解释algaorythm，可以向你保证 – @OmnipotentEntity是正确的 – 我知道它更好后，向你解释:)
到目前为止，我已经在以下链接中find了最好的解释之一：
http://tarokuriyama.com/projects/palindrome2.php
它还具有可视化的问题中提到的第一个链接使用相同的string示例（babcbabcbaccba）。
除了这个链接，我还发现了代码
http://algs4.cs.princeton.edu/53substring/Manacher.java.html
我希望对于那些试图理解这个algorithm的症结的人来说，这会有所帮助。
全文： http : //www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/
首先让我们仔细观察回文，以便find一些有趣的属性。 例如，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 =原始string的长度。 例如，
我'ci ----------------------------------------------- ------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
-------------------------------------------------- ---
T1 = | $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
-------------------------------------------------- ---
接下来，观察到从中心c周围的（变换的）回文T的对称性，对于0≤k≤c，T [ck] = T [c + k]。 这是位置ck和c + k是彼此镜像。 换句话说，对于中心c右侧的索引i，镜像索引i'在c的左边，使得c-i'= ic => i'= 2 * ci，反之亦然。 那是，
对于回文子串的中心c右侧的每个位置i，i的镜像位置是i'= 2 * ci，反之亦然。
让我们定义一个数组P [0..2 * n]，使得P [i]等于以i为中心的回文的长度。 请注意，长度实际上是通过原始string中的字符数（通过忽略特殊字符$）来衡量的。 也让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'如下图所示。
最小我最大
-------------------------------------------------- ---
| 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的最大元素来find最长的回文子串的长度。也就是说，
P [i]是在变换后的stringT中以i为中心的回文子string的长度，即。 以原始stringS为中心在i / 2处; 因此，最长的回文子串将是从索引（i max -P [i max ]）/ 2开始的长度P [i max ]的子串，使得i max是P中的最大元素的索引。
让我们在下面为我们的非回文示例stringS =“babaabca”画一个类似的图。
最小c最大
| ---------------- | ----------------- |
-------------------------------------------------- ------------------
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。 对称性提示了下面的情况，我们可能用它来计算P [i]，通过使用左边镜像索引i'的先前计算的P [i']，因此跳过了很多计算。 假设我们有一个参考回文（第一个回文）开始。
-
如果第二次回文在第一次回文的范围内，则第三次回文的中心位于第一次回文的右侧，与第二次回文的长度完全相同。至less一个字符。
例如在下图中，以第一个回文中心在c = 8且以min = 4和max = 12为界，以i = 9为中心的第三回文长度（具有镜像索引i'= 2 * ci = 7）是，P [i] = P [i'] = 1。这是因为以i'为中心的第二个回文在第一个回文的范围内。 同样，P [10] = P [6] = 0。
| ---- ---- 3 | | ---- ---- 2号| | -----------第一回文logging--------- | 最小我最大 | ------------ | --- | --- | ------------- | -------------------------------------------------- ------------------ 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 | ？ | ？ | ？ | ？ | ？ | ？ | ？ | ？ | -------------------------------------------------- -------------------现在问题是如何检查这种情况？ 请注意，由于对称属性，段[min..i']的长度等于段[i..max]的长度。 另外请注意，如果第二次回文的左边缘位于第一回文的最小边界内，第二次回文完全位于第一次回文内。 那是，
i'-P [i']> = min => P [i'] - i'<-min（negate） => P [i'] <i'-min => P [i'] <max-i [（max-i）=（i'-min）由于对称性]。结合案例1中的所有事实，
P [i] = P [i']，iff（max-i）> P [i']
-
如果第二个回文符合或超出第一个回文的左边界，则第三个回文确保至less具有从第一个回文的中心到右边最外边字符的长度。 从第二回文中心到第一回文的左边最外侧字符的长度是相同的。
例如在下图中，以i = 5为中心的第二个回文延伸超过第一个回文的左边界。 所以，在这种情况下，我们不能说P [i] = P [i']。 但是第三个回文的长度集中在i = 11，P [i]至less是从中心i = 11到第一个回文的右边界最大= 12的长度，集中在c。 也就是说，P [i]> = 1。 这意味着第三次回文可以超过最大值，当且仅当下一个过去的最近的字符与镜像字符完全匹配时，我们继续这个检查。 例如，在这种情况下，P [13]！= P [9]，它不能被扩展。 所以P [i] = 1。
| -------第二回文------ | | ---- ---- 3 | ---？ | -----------第一回文logging--------- | 最小我最大 | ---- | ----------- | ----------- | ----- | -------------------------------------------------- ------------------ 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的失败检查。也就是说，第二回文将延伸经过第一回文的左边缘iff，
i'-P [i'] <min => P [i'] - i'> = -min [negate] => P [i']> = i'-min => P [i']> = max-i [（max-i）=（i'-min）由于对称性]。也就是说，P [i]至less是（max-i）iff（max-i）P [i]> =（max-i），iff（max-i）现在，如果第三次回文延伸超过max，我们需要更新新回文的中心和边界。
如果以i为中心的回文确实超过max，那么我们有新的（扩展的）回文，因此在c = i处有一个新的中心。 将最大值更新到新回文的最右边界。
结合案例1和案例2的所有事实，我们可以想出一个非常漂亮的小公式：
情况1：P [i] = P [i']，iff（max-i）> P [i'] 情况2：P [i]> =（max-i），iff（max-i）= min（P [i']，max-i）。也就是说，当第三次回文不能延伸超过最大值时，P [i] = min（P [i']，max-i） 否则，我们有新的第三个回文中心在c = i和新的max = i + P [i]。
-
第一个回文和第二个回文没有提供帮助确定第四个回文的回文长度的信息，第四个回文的中心位于第一个回文的右边。
也就是说，如果i> max，我们不能先确定P [i]。 那是，
P [i] = 0，iff max -i <0
结合所有的情况，我们得出公式：
P [i] = max> i？ min（P [i']，max-i）：0。如果我们可以扩展超过max，那么我们通过匹配超过max的字符和镜像字符来扩展c = i的新中心。 最后，当我们有一个不匹配的时候，我们更新新的最大=我+ P [我]。
参考： wiki页面中的algorithm描述
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; }
我使用animationgraphics制作了这个algorithm的video。 希望这会帮助你理解它！ https://www.youtube.com/watch?v=kbUiR5YWUpQ
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 // ie "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> // ie abccba anchor = 3: position of 2nd 'c', dist = 3 // looking if next char has a dist. of 3 from previous one // ie 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) // ie "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 //ie "......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定义为以每个字符为中心的最长的回文子串的长度。
关键是，当较长的回文完全embedded较长的回文时，T [i]在长回文内也应是对称的。
否则，我们将不得不从头开始计算T [i]，而不是从对称的左边部分引出。
