关键词：
引子
1. 先讲个歪果仁的故事，在庞贝古城的废墟中，有一座名为赫库兰尼姆的城市，在这个遗迹中人们发现一块石碑，石碑上写着一个非常有趣的拉丁串：sator arepo tenet opera rotas翻译到中文大概意思是：一个叫做arepo的耕作者，他用力地把着车轮。
这样排列一下，从上下左右读都是一样的，歪果仁挺会完的。
2. 让我印象更深刻的是高中老师给我们讲的一个故事，有一天宋代著名文学家苏轼和他的妹妹苏小妹正在荡舟湖上，欣赏着风景，忽然有人呈上秦少游捎来的一封书信。打开一看，原来是一首别出心裁的回文诗：
苏小妹看罢微微一笑，立即看出其中的奥秘，读出了这首叠字回文诗：
静思伊久阻归期，
久阻归期忆别离；
忆别离时闻漏转，
时闻漏转静思伊。
苏小妹被丈夫的一片痴情深深感到动，心中荡起无限相思之情。面对一望无际的西湖美景，便仿少游诗体，也作了一首回环诗，遥寄远方的亲人：
采莲人在绿杨津，
在绿杨津一阕新；
一阕新歌声漱玉，
歌声漱玉采莲人。
苏东坡在一旁深为小妹的过人才智暗暗高兴，他也不甘寂寞，略加沉吟，便提笔写了如下一首：
赏花归去马如飞，
去马如飞酒力微；
酒力微醒时已暮，
醒时已暮赏花归。
苏氏兄妹也派人将他们的诗作送与秦少游。
老师讲完这个故事我就感觉古人写诗都是开挂的，这些诗倒过来还是一首完整诗，都是叠字回文诗。
故事是好故事，可是本人不太会讲故事，关于回文的趣事还有很多，想看故事的可以自己去找。
正文
问题：给你一个字符串长度为n，现在让你求出这个字符串最长回文子串的长度。
解法一：
纯暴力，找出这个字符串的所有子串，然后判断每个子串是否是回文串，维护更新最大的长度即可。空间复杂度O(1)，时间复杂度O(n^3)。
解法二：
解法一实在是太暴力了，换个思路暴力，长度为奇数的回文串以中间字符为对称轴成轴对称，长度为偶数的回文串以中间空隙为对称轴成轴对称。那么我们不就可以枚举对称轴，同时比较左右两边的字符，直到左右两边出现的字符不同或者达到边界。枚举的过程中维护更新最大长度即可。空间复杂度O(1)，时间复杂度O(n^2)。虽然也很暴力，但是比解法一比起来就好太多了。
解法三：
上面的解法都有很多重复计算的地方，我们存储已计算的内容，之后直接使用，那么就能进一步优化时间复杂度，这是典型的空间换时间的思路。解法二有一些值得学习的地方，但是还存在问题，除了重复计算，还有就是分奇偶，相当于要进行两次处理。
1. 先解决分奇偶的问题
为了避免分奇偶讨论，我们可以对原字符串进行一些处理，在原字符串中插入一些字符：
abcba 转化为 #a#b#c#b#a#
abccba 转化为 #a#b#c#c#b#a#
进行上面的处理后整个字符串的长度肯定为奇数，而且，不改变原串的回文结构。要保证这点我们选择插入的字符一定要是原串中不存在的。
2. 避免重复计算
我们先来看看解法二中哪里就有重复计算了
a b a b a
0 1 2 3 4
以1为对称轴时，我们已经遍历了aba，当以2为对称轴的时候其实又遍历了一遍aba，左边的子串aba被遍历了两次。其实遍历过的部分只要提取出有用的部分保持下来就无需再遍历了。
回文半径：最左或最右位置的字符与其对称轴的距离。
现在申请一个数组LR，LR[i]表示以i为对称轴的回文半径。
| # | a | # | b | # | c | # | b | # | a | # | |
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| LR | 1 | 2 | 1 | 2 | 1 | 6 | 1 | 2 | 1 | 2 | 1 |
| LR-1 | 0 | 1 | 0 | 1 | 0 | 5 | 0 | 1 | 0 | 1 | 0 |
我们发现，max(LR-1)即时我们要求的结果。
现在问题就转化为：怎么快速的得到LR数组了。
现在再约定一个值MaxRight，MaxRight表示当前所遍历到的所有回文子串中，最靠右的索引。
pos为对称轴，从左往右地遍历字符串来求RL，假设当前访问到的位置为i，即要求RL[i]，在对应上图，i必然是在pos大（pos和pos前的已经求解完成）。但是i和MaxRight的相对关系并不确定。
1. i在MaxRight的左边
从图上观察，我们可以利用已知部分来初步确定下LR[i]的值，假设i关于pos的对称点时j，现在我们来梳理一下已知量：LR[j]，MaxRight，pos，其中j = 2*pos - i.
假设LR[j]比较短，整体就包含在红色区间内，那么由于对称性LR[i]≥LR[j].
现在RL[j]不完全包含在红色区间内，上面JL等于JR关于j对称，IL等于JR、JL等于IR关于pos对称，那么IL等于IR，也就是说LR[i]≥MaxRight-i.
通过上面两种情况的讨论，求解LR[i]的使用利用了已知部分的信息，避免了重复遍历，我们可以得到LR[i] ≥ min(LR[j], MaxRight-i])，这个就很强。
对于后面还不确定的长度继续遍历即可，此时遍历的都是之前没有遍历过的。
2. i在MaxRight的右边
这种无需利用已知信息（也用不上），直接遍历未知部分，更新MaxRight和pos即可。
一句话总结一下，上面我们在干嘛，怎么就优化了复杂度：维护MaxRight和pos，在更新RL[i]时避免了重复计算。
code:
1 const int MAXN = 1000010; 2 char Ma[2*MAXN]; // 插入字符后的原数组 3 int LR[2*MAXN]; // LR 4 int MR = 0; // MaxRight 5 int pos = 0; // pos 6 7 void Manacher(char s[], int len) 8 { 9 int l = 0; 10 11 // 处理原数组 12 Ma[l++] = 'S'; 13 Ma[l++] = '#'; 14 for (int i = 0; i < len; ++i) { 15 Ma[l++] = s[i]; 16 Ma[l++] = '#'; 17 } 18 Ma[l] = 0; 19 20 for (int i = 0; i < l; ++i) { 21 22 // 利用已知信息，避免重复计算 23 LR[i] = MR > i ? min(LR[2*pos-i], MR-i) : 1; 24 25 // 继续找 26 while (Ma[i+LR[i]] == Ma[i-LR[i]]) { 27 ++LR[i]; 28 } 29 30 // 更新MaxRight pos 31 if (i + LR[i] > MR) { 32 MR = i +LR[i]; 33 pos = i; 34 } 35 } 36 }
算法空间复杂度O(n)，时间复杂度O(n)，这个稍微解释下，虽然代码里面是两重循环，由于内层的循环只对尚未遍历的部分进行，因此对于每一个字符而言，只会进行访问一次。
34:回文子串
34:回文子串查看提交统计提问总时间限制: 1000ms 内存限制: 65536kB描述给定一个字符串，输出所有长度至少为2的回文子串。回文子串即从左往右输出和从右往左输出结果是一样的字符串，比如：abba，cccdeedccc都是回... 查看详情
回文子串
...: 65536kB描述给定一个字符串，输出所有长度至少为2的回文子串。回文子串即从左往右输出和从右往左输出结果是一样的字符串，比如：abba，cccdeedccc都是回文字符串。输入一个字符串，由字母或数字组成。长度500以内。输出... 查看详情
最长回文子串
】最长回文子串【英文标题】：LongestPalindromicsubstring【发布时间】：2017-04-0512:06:20【问题描述】：我一直在解决一些问题来为我的期中考试做准备，但我无法弄清楚是什么导致了这个错误。问题表明"问题是寻找一个最大长度的... 查看详情
1088最长回文子串
1088最长回文子串（51NOD基础题）基准时间限制：1秒空间限制：131072KB分值:0难度：基础题 回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str，输出Str里最长回文子串的长度。Input输入Str（Str的长度 ... 查看详情
[hot100]回文子串与最长回文子串(代码片段)
647.回文子串中等题回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。①动态规划状态：dp[i][j]表示字符串s在[i,j]区间的子串是否是一个回文串。状态转移方程：当s[i]=&#... 查看详情
求最长回文子串，o（n）复杂度
最长回文子串问题—Manacher算法最长回文串问题是一个经典的算法题。0.问题定义最长回文子串问题：给定一个字符串，求它的最长回文子串长度。假设一个字符串正着读和反着读是一样的，那它就是回文串。以下是一些回文串... 查看详情
回文子串(代码片段)
...：给定一个字符串，计算这个字符串中有多少个回文子串（回文串是一个正读和反读都一样的字符串）。具有不同开始位置或结束的回文串，即使是由相同的字符组成，也会被计为是不同的子串。分析... 查看详情
如何寻找最长回文子串(代码片段)
回文串是面试常常遇到的问题（虽然问题本身没啥意义），本文就告诉你回文串问题的核心思想是什么。首先，明确一下什：回文串就是正着读和反着读都一样的字符串。比如说字符串aba和abba都是回文串，因为它们对称，反过... 查看详情
算法最长回文子串longestpalindromesubstring
对于字符串S，要找到它最长的回文子串，能想到的最暴力方法，应该是对于每个元素i-th都向左向右对称搜索，最后用一个数组span记录下相对应元素i-th为中心的回文子串长度。那么问题来了： 1.这样的方法，对于奇回文子串... 查看详情
ac日记——回文子串openjudge1.734
34:回文子串总时间限制: 1000ms 内存限制: 65536kB描述给定一个字符串，输出所有长度至少为2的回文子串。回文子串即从左往右输出和从右往左输出结果是一样的字符串，比如：abba，cccdeedccc都是回文字符串。输入一个字... 查看详情
leetcode647.回文子串(palindromicsubstrings)(代码片段)
647.回文子串647.PalindromicSubstrings题目描述给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。LeetCode647.PalindromicSubstrings... 查看详情
51nod1088最长回文子串
/*1088最长回文子串基准时间限制：1秒空间限制：131072KB分值:0难度：基础题收藏关注回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str，输出Str里最长回文子串的长度。Input输入Str（Str的长度<=1000)Output... 查看详情
最长回文子串澄清
】最长回文子串澄清【英文标题】：LongestPalindromicSubstringclarification【发布时间】：2017-02-2801:37:11【问题描述】：方法#3（动态编程）[接受]为了改进蛮力解决方案，我们首先观察我们如何能够在验证回文时避免不必要的重新计算... 查看详情
[leetcode]longestpalindromicsubstring最长回文子串
Givenastring S,findthelongestpalindromicsubstringin S.Youmayassumethatthemaximumlengthof S is1000,andthereexistsoneuniquelongestpalindromicsubstring.做这道题之前要先了解什么是回文子串。回文串通俗的解释是，分别从 查看详情
找到最长的回文子串
】找到最长的回文子串【英文标题】：Findthelongestpallindromesubstring【发布时间】：2015-08-0406:51:21【问题描述】：给定一个字符串，找出最长的回文子串。例如，如果给定的字符串是“forgeeksskeegfor”，则输出应该是“geeksskeeg”。我... 查看详情
字符串最长回文子串(动态规划算法)★(代码片段)
文章目录一、回文串、子串、子序列二、最长回文子串1、动态规划算法2、动态规划算法代码示例一、回文串、子串、子序列"回文串(Palindrome)"是正反都一样的字符串,abccba,001100等字符串;给定一个字符串"abcd","子串(... 查看详情
最长回文子串
classSolution{public:/***@paramsinputstring*@returnthelongestpalindromicsubstring*/stringlongestPalindrome(string&s){//Writeyourcodehereusingnamespacestd;constintlength=s.size();if(length==0){retu 查看详情
1089最长回文子串(代码片段)
1089 最长回文子串 V2（Manacher算法） 基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str，输出Str里最长回文... 查看详情