最长回文子串（含manacher算法）

题目：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 长度最长为1000。

解答：

法一：先找到两两配对的，例如bab,bb这样的形式，再扩展

class Solution {
public:
    string tostr(char c){
        string s;
        stringstream ss;
        ss<<c;
        ss>>s;
        return s;
    }
    
    string longestPalindrome(string s) {
        vector<int> vec;
        int i,max=0;
        string rs="";
        
        if(s.length()==1)
            return s;
        
		//寻找两两配对
        for(i=0;i<s.length()-2;i++){
            if(s[i]==s[i+2] && s[i]==s[i+1])
            {
                vec.push_back(i);
                i+=2;
            }
            else if(s[i]==s[i+2])
                vec.push_back(i);
            else if(s[i]==s[i+1])
                vec.push_back(i);
		}
        if(i<s.length()-1 && s[i]==s[i+1])
			vec.push_back(i);

        //遍历vec，扩展取最大长度串 
        int distance;
        string sstr;
        for(int j=0;j<vec.size();j++){
        	int pos=vec[j],d=0;
			distance=0;sstr="";
        	if(s[pos]==s[pos+2])
        	{
        		sstr=tostr(s[pos])+tostr(s[pos+1])+tostr(s[pos+2]);
				d=pos+3;
				distance=3;
        	}
			else
        	{
        		sstr=tostr(s[pos])+tostr(s[pos+1]);
				d=pos+2;
				distance=2;
        	}
        	for(int k=pos-1;k>0;k--){
        		if(s[k]==s[d])
        		{
        			sstr=tostr(s[k])+sstr+tostr(s[d]);
					distance++;
        		}
				else
        			break;
			}
			
			//更新最长回文串
			if(max<distance) 
			{
				max=distance;
				rs=sstr;
			}
		}
		return rs;
    }
};

法二：manacher算法

算法详解: https://segmentfault.com/a/1190000008484167

class Solution {
public:
    string longestPalindrome(string s) {
        char str[s.size()*2+10];
        int n=0;
        //填充#使奇偶性一致
        str[n++]='#';
        for(int i=0;i<s.size();i++){
            str[n++]=s[i];
            str[n++]='#';
        }
        str[n]='\0';
        
        int p[n+1],mx=0,pos=0;            //mx为最右，pos为对称轴
        memset(p,1,sizeof(p));
        //遍历求p数组
        for(int i=1;i<n;i++){
            //重点步骤!
            if(i<mx)
                p[i]=min(p[2*pos-i],mx-i);
            else
                p[i]=1;
            
            //扩充
            while(i >= p[i] && str[i+p[i]]==str[i-p[i]]){
                   p[i]++;
            }
            
            //更新mx和pos
            if(i+p[i] > mx){
                mx = i+p[i];
                pos = i;
            }
        }
        
        //求最长回文串
        mx=p[1];pos=1;
        for(int i=1;i<n;i++)
        {
            if(p[i] > mx){
                mx=p[i];
                pos=i;
            }
        }
        mx-=1;
        string r="";
        for(int i=pos-mx+1;i<pos+mx;i+=2)
           r.push_back(str[i]);
        
        return r;
    }
};