5. 最长回文子串

暴力寻找O(n^3)的复杂度，枚举每一个连续子串，判断其是否是回文。
这种方法没有做，会超时。

中心扩展法O(n^2)的复杂度，对每一个字符向两边进行扩展，判断是否是回文子串，
这样解决了奇数长度的子串，然后对任意两个字符的空隙进行扩展，进行判断，可以解决偶数长度的子串。
总共进行2*n-1次的扩展

    string longestPalindrome(string s) {
        string res="";
        if(!s.length()) return res;
        if(s.length()==1) return s;
        int start=0,end=0;
        for(int i=0;i<s.length();i++){
            int len1=expandAroundCenter(s,i,i);
            int len2=expandAroundCenter(s,i,i+1);
            int len=max(len1,len2);
            if(len>end-start) {
                start=i-(len-1)/2;
                end=i+len/2;
            }
        } 
        return string(s,start,end-start+1);
    }
     int expandAroundCenter(string s,int left,int right){//扩展的过程，返回其长度
         int l=left,r=right;
         while(l>=0&&r<s.length()&&s[l]==s[r]){
             l--;
             r++;
         }
         return r-l-1;
     }

Manacher算法

可以在O(n)的时间内找出最长回文子串，初次学习这个算法，网上找了好几篇博客，看了好长时间才理解了，有点神奇。
子串长度有奇有偶，处理起来很麻烦，所以该算法对原字符串进行了填充，任意字符两边添加了’#‘，这样原字符串长度无论是奇数还是偶数，现在都是奇数，如abba长度位偶数数，处理之后#a#b#b#a# ,总长度变为奇数；aba长度为奇数，处理后#a#b#a#
长度仍然是奇数。
首尾则添加了不相同的两个字符用于防止越界。

char ns[4444];  //便是用来存储预处理后的数组
     int p[2010]; //p[i]存储 以i为中心点的回文串的半径
    string longestPalindrome(string s) {
      int len=Init(s); //进行预处理
      int maxlen=-1;  //初始化最大长度为-1
      int id; //始终是能伸到最右端的回文子串的中心位置
      int mx=0,x=0; //mx 回文子串能伸向最右边界，x是
      for(int i=1;i<len;i++){
          if(i<mx) p[i]=min(p[2*id-i],mx-i);  //i 在mx左边 最大化利用回文子串的特性，用p[j]来求p[i],也是这个算法的核心。
          else p[i]=1;//i超出了最右端，则初始化为1，然后向两端扩展
         while(ns[i-p[i]]==ns[i+p[i]]) p[i]++;

         if(mx<i+p[i]){  //当前i这个回文子串 的最右端超出了mx，id用i来替换，mx用i+p[i]替换
             id=i;
             mx=i+p[i];
         }

         if(p[i]>maxlen){ //用于保存最大回文子串的半径和中心位置
             maxlen=p[i];
             x=i;
            }
      }
      return  s.substr((x-maxlen)/2,maxlen-1);    //两个参数，一个起始位置，一个长度
    }
    int Init(string s){
     int len=s.length();
     ns[0]='$';
     ns[1]='#';
     int j=2;
     for(int i=0;i<len;i++){
         ns[j++]=s[i];
         ns[j++]='#';
     }
     ns[j]='\0';
     return j;
    }