////  main.cpp//  Longest Substring////  Created by Bowie Hsu  on 14/11/21.//  Copyright (c) 2014年 Bowie Hsu . All rights reserved.//#include <iostream>#include <string>#include <sstream>#include <vector>#include "stdio.h"#include "ctype.h"using namespace std;class Solution {public:    //预处理，将#号加入到原有的string中    string preprosess(string s)    {        int n=s.length();        //string oss;        stringstream oss;  //调用sstream中的stringstream        oss << ‘^‘;        for (int i=0; i<n; ++i)            oss<<"#"<<s[i];            oss<<‘#‘;            oss<<‘$‘;            return oss.str();            }        string longestPalindrome(string s) {              string output;        int mx=0;        int id=0;        string l=preprosess(s);        int n=l.length();        int *p=new int[n];        //Manacher算法        for(int i=1;i<n-1;++i)        {          //简便写法          p[i]=(mx>i)?min(mx-i, p[2*id-i]):1;                      while(l[i+p[i]]==l[i-p[i]])             ++p[i];          if(p[i]+i>mx)         {             mx=p[i]+i;             id=i;         }        }        //找到最大字串的位置与个数        int maxnum=0;        int center=0;        for (int i=1;i<n-1; ++i)        {   if(p[i]>maxnum)        {            maxnum=p[i];          center=i;        }        }    return s.substr((center-maxnum)/2,maxnum-1); //返回一个string    }   };int main(){    string input="ccd";    string ans;    Solution x;    ans=x.longestPalindrome(input);    cout<<ans<<endl;}