查看: 3368|回复: 12
收起左侧

经典问题 : 求字符串最大公共子串

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:经典问题 : 字符串的最大公共子序列
下一篇:Find the longest simple path
darksteel 2011-5-19 13:16:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
这个n^2的DP肯定也能做。总感觉能跟后缀的最长公共前缀扯上关系,但对那些知识不熟,不太确定能不能行
回复

使用道具 举报

头像被屏蔽
holyzz 2011-5-19 14:03:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

Imbalism 2011-9-24 14:21:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
string findSubString(const string& a, const string& b)
{
     size_t max = 0;
     size_t maxIndex = 0;
     vector<size_t> row(b.size() + 1, 0);
     vector< vector<size_t> > dp(a.size() + 1, row);
     for (size_t i = 0; i <= b.size(); ++i)
          dp[0][i] = 0;
     for (size_t i = 0; i <= a.size(); ++i)
          dp[i][0] = 0;
     for (size_t i = 1; i <= a.size(); ++i)
          for (size_t j = 1; j <= b.size(); ++j)
          {
               if (a[i-1] == b[j-1])
               {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if(dp[i][j] > max)
                    {
                         max = dp[i][j];
                         maxIndex = i - 1;
                    }
               }
               else
               {
                    dp[i][j] = 0;
               }
          }
     return a.substr(maxIndex - max + 1, max);
}

dp版本,应该有suffix tree版
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-9-25 10:08:51 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

Imbalism 2011-10-3 12:34:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
我觉得面试时候,可以先实现n *n 的,然后再讨论下n的解法。 不用实现
回复

使用道具 举报

ilhrx 2011-10-3 13:25:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
回复 5# wwwyhx


    O(n)的话应该是循环数组吧。。。感觉编程上来说不太麻烦

       dp[j] = dp[i-1][j-1] + 1;
        变成
         dp[a][j]=dp[j-1]+1;
  a表示上一个状态,b表示下一个状态, 每次循环的话,可以  a=1-a b=1-b; 这样的话是开了一个2n的数组
  难道没有时间上能够达到O(n log n)的解法么。。。求教啊。。。
回复

使用道具 举报

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

使用道具 举报

ilhrx 2011-10-4 12:46:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
回复 8# wwwyhx


    对。空间上的确是这么省的,所以开两个一维数组就够用了
回复

使用道具 举报

lambda2fei 2012-9-2 17:49:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
用后缀数组:建数组O(n),求解O(n)。。。。保证面试官都写不出来。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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