📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft(5) : 字符串最大回文子串

🔗
 楼主| wwwyhx 2011-4-23 11:10:53 | 只看该作者
全局:
一般的算法应该是O(n^2),suffix array能做到nlgn。

这题之前写过来了,不过觉得贴代码的话意义其实不大,因为一般很少人会有空去review别人的代码,看起来太麻烦,而且要理解别人的程序有时候不是一件很容易的事情。

其实版主是否能考虑贴题目的时候多贴一些Online Judge上的题目(USACO, POJ, TOPCODER)之类,这样大家能直接通过OJ来测试代码,而且能够知道自己写的对不对。自测的话很多时候测试数据都太少,很多问题都没办法测出来的
上代码应该是不知道自己的解法出了什么问题的时候,平时交流觉得还是伪代码或者idea更加简洁…… ...
danielgao 发表于 2011-4-23 10:43


伪代码也不错
回复

使用道具 举报

🔗
darksteel 2011-4-25 13:59:44 | 只看该作者
全局:
回复 7# wwwyhx
前两天出去了,后来我看了下我得程序,觉得只要更新最大值的时候加上判断i+j==l+dp[j]就能保证正确性,这样就是充分必要的了。这类错误我犯过很多次,以后得多加注意,就是方法能处理符合条件的情况,但不能排除某些实际不符合条件的情况,这时就要对加些限制条件,排除掉那些情况。
不过这个方法n^2的空间局限性太大,还是不太实用。。
回复

使用道具 举报

🔗
sing1ee 2012-10-1 08:48:48 | 只看该作者
全局:
dp的话,想到个n^2的,比较直接dp[i][j]为1,代表是回文,0代表不是回文。
回复

使用道具 举报

🔗
tankadozmy 2012-10-1 09:14:34 | 只看该作者
全局:
我原来的做法是正反串拼接, 然后快排后缀数组, 顺序查找的时候注意串是否来一个串来自正序的串, 一个来自逆序的串. 至少可以行的通~ n.lgn
回复

使用道具 举报

🔗
xiongli.cs 2012-10-1 10:34:15 | 只看该作者
全局:
用suffix array,这是许智磊那篇论文里的例子题
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表