Manacher算法--O（n）内求回文子串

class Solution {
private:
	string stmp;
	string init(string s)
	{
		string ret="$";
		for(int i=0;i<s.size();i++)
		{
			ret+="#"+s.substr(i,1);
		}
		ret+="#";
		return ret;
	}
	void Manacher(int len,string str,int *p)
	{
		int mx=0;
		int id;
		p[0]=0;
		for(int i=1;i<len;i++)
		{
			
			p[i]=1;
			if(mx>i)
			{
				p[i]=min(p[2*id-i],mx-i);
			}
			while(str[i-p[i]]==str[i+p[i]]) p[i]++;
			if(i+p[i]>mx)
			{
				id=i;
				mx=i+p[i];
			}
		}
	}
public:
    string longestPalindrome(string s) 
    {
        string str=init(s);
        int *p=new int[str.size()];
        Manacher(str.size(),str,p);
        int ans=0,index=0;
        for(int i=1;i<str.size();i++)
        {
        	if(p[i]>ans)
        	{
        		ans=p[i];
        		index=i;
        	}
        }
        delete []p;
        return s.substr((index-ans)/2,ans-1);
    }
};

class Solution {
public:
    string longestPalindrome(string s) 
    {
        int m=1,beg=0,end=0;
        int len=s.size();
        bool flag[len][len];
        for(int i=0;i<len;i++)
        	for(int j=0;j<len;j++)
        	{
        		if(i>=j) flag[i][j]=true;
        		else flag[i][j]=false;
        	}
        for(int j=1;j<len;j++)
        	for(int i=0;i<j;i++)
        	{
        		if(s[i]==s[j])
        		{
        			flag[i][j]=flag[i+1][j-1];
        			if(flag[i][j]&&j-i+1>m)
        			{
        				beg=i;
        				end=j;
        				m=j-i+1;
        			}
        		}
        		else
        			flag[i][j]=false;
        	}
        return s.substr(beg,m);
    }
};