首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

关于最长回文子串的有关问题

2012-09-23 
关于最长回文子串的问题输入一个字符串str,要求输出str里的最长回文子串。

关于最长回文子串的问题
输入一个字符串str,要求输出str里的最长回文子串。



===========================================
分类枚举,偶数长度的回文和奇数长度的回文。
如果是奇数长度的回文,枚举中心字符的位置,向两边逐步扩展,一旦失败马上枚举下一个。
偶数的类似。

想不到其他特别好的方法了。
大家有别的好方法吗?

[解决办法]

探讨
我以前也犯过同样的错误。

n^2的方法就是枚举每个字符,依次统计回文的长度。
有个近似O(n)的方法,不过真的很复杂,有些类似于dp,到现在我对该方法还是迷迷糊糊的。


引用:
输入str
取str的逆序列str2
这时就转化为求str与str2的最长公共子序列的问题 这个有现成算法的吧

热点排行