查看: 4458|回复: 14
收起左侧

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

|只看干货
头像被屏蔽
wwwyhx | 显示全部楼层 |阅读模式
Imbalism 2011-4-22 16:19:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
用后缀树将S和S.reverse()插入
for i [1 to n - 1]
   找出S[0 - i].reverse() 与 S[i, n]的LCA
   找出S[0 - i].reverse() 与 S[i + 1, n]的LCA
从些个LCAs里面选出最大的1
复杂度O(n)

不知道对不对,烦请指正
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-22 17:09:48 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

darksteel 2011-4-22 21:03:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
本帖最后由 darksteel 于 2011-4-22 21:07 编辑

这题以前做过类似的,用的是枚举回文子串中心,然后向两边检查的方法,要检查奇数和偶数的情况,最坏O(n^2)。为了拓宽思路,这里给出另一种dp原串和逆串最长子串的方法,比较简练,细节不多不容易出错,代码如下:
  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. using namespace std;
  5. string LongestSubPal(string s)
  6. {
  7.         int i, j, l = s.length(), maxp, maxl = 0;
  8.         int dp[200][200];
  9.         memset(dp, 0, sizeof(dp));
  10.         for(i = 1; i <= l; i++)
  11.                 for(j = 1; j <= l; j++)
  12.                         if(s[i-1] == s[l-j]) {
  13.                                 dp[i][j] = dp[i-1][j-1]+1;
  14.                                 if(dp[i][j] > maxl) {
  15.                                         maxl = dp[i][j]; maxp = i;
  16.                                 }
  17.                         }
  18.         return s.substr(maxp-maxl, maxl);
  19. }
  20. int
  21. main() {
  22.         string s;
  23.         while(cin >> s) {
  24.                 cout << LongestSubPal(s) << endl;
  25.         }
  26.         return 0;
  27. }
复制代码

补充一下,这种方法复杂度O(n^2),对大多数情况可能还不如上面提到的那种方法,仅作为一种思路。
不过这题想降到n^2一下恐怕必须要用数据结构,编程复杂度就大了。
回复

使用道具 举报

Narashy 2011-4-22 23:47:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (23)
 
 
4% (1)    👎
这个字串是连续的还是不连的啊?
连续的直接原串和逆传kmp
不连续就楼上dp,或者suffix array
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-23 09:35:01 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-23 09:37:11 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

danielgao 2011-4-23 10:43:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (86)
 
 
3% (3)    👎
本帖最后由 danielgao 于 2011-4-23 10:53 编辑

一般的算法应该是O(n^2),suffix array能做到nlgn。

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

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

使用道具 举报

darksteel 2011-4-23 10:58:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 6# wwwyhx
200只不过是随便设了个范围。你说的那个反例是对的,这个不是充分必要的,但应该可以通过对i,j和长度作检查来排除掉错误的情况。。。至于为什么这么做,不是就是想多试些思路吗,前面也说了枚举中心然后往两边查肯定能出来,以前做过
回复

使用道具 举报

darksteel 2011-4-23 11:05:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
我在想j的范围可以取i+j<=l,然后必须i+j+dp[i][j]-2==n才去更新maxl和maxp。不过如果多做检查,那就不简洁了倒是真的。。。
回复

使用道具 举报

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

本版积分规则

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