首页 > 其他 > 详细

[经典] 回文问题(三)

时间:2016-04-22 18:22:33      阅读:129      评论:0      收藏:0      [点我收藏+]

Longest Palindromic Substring 最长回文子串

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

普通做法,动态规划O(N^2)是能直接出结果的,长度从小到大排列,可以边动规边记录最大值。

 

Shortest Palindrome 最短回文生成

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

普通做法,即找到从头开始的最长的回文,复杂度为O(N^2);然后补齐。

 

事实上,找到以某个点为中心的最长回文子串的经典算法是 Manacher算法,复杂度为O(N),可求出以字符串中各个点为中心的子串。Manacher算法可参考http://blog.csdn.net/ggggiqnypgjg/article/details/6645824/

 

[经典] 回文问题(三)

原文:http://www.cnblogs.com/littletail/p/5372747.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!