程序员笔试题---【最大回文子串】
最大的回文字串，相信大家都很熟悉了，类似的题目有过很多。
单纯的有求解字符串中的最大回文字串，例如：“abcgoogleaba”，最大的回文字串为goog，虽说aba也是回文但长度较短。
还有网易游戏考到的一道题：“abcgoogleaba”，如果是回文的话，当做一个整体输出，否则单个的输出，这个输出的格式为：a,b,c,goog,l,e,aba.
针对求最大的回文字串问题。有很多种方式，比如蛮力法。但是相信大家在笔试或者面试的时候，考官都会要求尽量的好的时间和空间复杂度。
因此我们需要寻找更好的办法。
第一、最大的回文字串1、一般的做法，分为回文串是偶数个还是奇数个就如上面的例子一样：abcgoogleaba，两个回文，一个是goog，另一个是：aba
2、将偶数个奇数个统一起来如何统一，这是个问题？
我们可以这样，在每个字符之间插入一个特殊的字符。
比如上面的字符串：abcgoogleaba。可以进行这样的操作：#a#b#c#g#o#o#g#l#e#a#b#a#
这样回文的字串就都是奇数的情况，就不需要考虑偶数的情况。
3、上面的做法的时间复杂度依然不是很理想的下面我们用更好的点做法O(n)
int getMaxHuiWenCharP(char *s,int len){int nLen=2*len+3;char *str =new char[nLen];int i=0;int max=0;str[0]='$';str[1]='#';for(;i<len;i++){str[i*2+2]=s[i];str[i*2+3]='#';}str[nLen-1]=0;int *p=new int[nLen];//定义一个用于标记的int数组for(i=1;i<nLen;i++){cout<<str[i];p[i]=0;}cout<<endl;int id=0;for(i=1; i<nLen; i++) { if( max > i ) p[i] = MIN( p[2*id-i], p[id]+id-i );//这里定义一个MIN的宏 else p[i] = 1; for(; str[i+p[i]] == str[i-p[i]]; p[i]++) NULL; if( p[i] + i > max ) { max = p[i] + i; id = i; } }int mx=0;for(i=1;i<nLen;i++){if(mx<p[i]-1)mx=p[i]-1;}return mx;}第二、网易游戏笔试题根据上面提供的方式，大家先柔和下咯！
欢迎大家t提供更好的办法哈！
