【回文字符串】 最长回文子串O(N) Manacher算法

原理讲的清晰:Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串

注意:

①动态生命P[]和newStr数组后,不要忘记delete[] //其实这是基本的编码习惯

②最终返回结果是P[i]-1

下面是自己写的Manacher函数

int manacher(char *src){
int srcLen=strlen(src);
int len=*srcLen+;
char *newStr=new char[len];//还是+3??要不要给\0留个位置??不用
int *P=new int[len];
int i,rst=;
//处理字符串
newStr[]='$';
newStr[]='#';
for(i=;i<srcLen;i++){
newStr[*i+]=src[i];
newStr[*i+]='#';
} //关键步骤:求P[i]
int id=;
int mx=;
P[]=;
for(i=;i<len;i++){
if(mx>i)
P[i]= MIN(mx-i , P[*id-i]);
else
P[i]=;
while(newStr[i+P[i]] == newStr[i-P[i]])
P[i]++;//据说这一步永远不会成立
//更新id和mx
if(P[i]+i > mx){
id=i;
mx=P[i]+i;
}
} //找到P[i]中最大值,注意最终返回的结果是P[i]-1
for(i=;i<len;i++)
if(rst<P[i])
rst=P[i]; delete[] P;
delete[] newStr;
return rst-;
}

参考代码:http://blog.csdn.net/ggggiqnypgjg/article/details/6645840 用定长的char数组

http://blog.csdn.net/bruce_zeng/article/details/8629572 new动态声明后没有delete

http://blog.csdn.net/pi9nc/article/details/9251455

上一篇:7.Swift翻译教程系列——控制循环的流程


下一篇:springMVC文件上传优化