首页 > 代码库 > 【回文字符串】 最长回文子串O(N) Manacher算法
【回文字符串】 最长回文子串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=2*srcLen+2; char *newStr=new char[len];//还是＋3？？要不要给\0留个位置？？不用 int *P=new int[len]; int i,rst=0; //处理字符串 newStr[0]=‘$‘; newStr[1]=‘#‘; for(i=0;i<srcLen;i++){ newStr[2*i+2]=src[i]; newStr[2*i+3]=‘#‘; } //关键步骤：求P[i] int id=0; int mx=0; P[0]=1; for(i=1;i<len;i++){ if(mx>i) P[i]= MIN(mx-i , P[2*id-i]); else P[i]=1; 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=0;i<len;i++) if(rst<P[i]) rst=P[i]; delete[] P; delete[] newStr; return rst-1; }
参考代码：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
【回文字符串】 最长回文子串O(N) Manacher算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。