本文共 1205 字，大约阅读时间需要 4 分钟。

问题描述：给定一个字符串，找出其中长度最长的回文子串。子串意思是给定字符串的连续子集。回文是指正序和倒序表现形式一样的字符串。

暴力算法是依次以每个点为中心展开并将对应位置的字符进行匹配，找出最长的子串即可。但是时间复杂度很高。这里介绍一种技巧性比较强的Manacher算法，时间复杂度只有O(n)。Manacher算法核心思想就是利用回文子串的对称性，假如某个中心点p包含在一个长的回文子串F中，则以该中心点为中心的回文子串会和以F的中心点为对称轴的另一侧的某个子串有一些共同的特征。利用这个属性就不需要为每个中心点再从1开始展开了。比如对于下面这个例子

                       abcdcgcdcbe

对该字符串依次进行扫描。假设现在已经找到的最长回文子串的中心为g,半径为5. 然后现在扫描到g右边的d位置。一般情况是你需要对每个中心点以半径为0依次展开，但是利用对称性却可以不必如此。比如到d的位置，通过计算发现d在当前最大的回文子串内，说明以g为对称点的左半部分和与以该d为中心点的回文子串有一些相似性。而前面这些点的回文子串都已经算好了。比如这里d的回文子串的一部分从左边可以得到，当然实际的回文子串可能会比这个大。

需要注意的是回文子串分两种，分别为abc，和abba类型。就是一个中心点为字母，一个中心点为空字符。为了在算法中一视同仁，Manacher在字符串中插入了特殊字符，比如将abc通过插入‘#’字符，变成#a#b#c#，这样就保证，每个回文子串都必须是以字符为中心的，因为插入特殊字符后，不可能存在两个相邻的字符相等，也就是不会出现abba这种形式的回文子串了。

下面上源代码

class Solution {public:    string longestPalindrome(string s) {        int len = s.length();        if(len == 1 || len == 0)return s;                string tmp="#";        for(int i=0;i
   
     j)?p[j]:(mx-i);            }//如果不在            else p[i] = 1;                        while(i+p[i]
    
     =0 && tmp[i+p[i]] == tmp[i-p[i]])p[i]++;//在已知信息上拓展                        if(p[i] > mx){                mx = p[i];                id = i;            }        }                string s1="";        for(int i=id-mx+1;i
    
   

转载地址：http://siqxi.baihongyu.com/