longest common prefix 和 longest common substring - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

longest common prefix 和 longest common substring

longest common prefix 和 longest common substring# JobHunting - 待字闺中

j*22012-09-04 07:09

1 楼

longest common prefix:
这题就只有O(n*m)的解法了吧？n=最短的一个string的长度，m=string个数。
没更简便的了吧？
longest common substring:
这题的两种解法都要掌握吗？DP比较容易，但是时间复杂度要O(n1xn2)。suffix tree
时间复杂度是O(n1+n2)，但是貌似很复杂，很想放弃了。有经验的大牛们，这题需要掌
握suffix算法吗？

j*22012-09-04 07:09

2 楼

没人对这俩问题感兴趣吗？还是答案太显而易见

tree

【在 j******2 的大作中提到】

: longest common prefix:
: 这题就只有O(n*m)的解法了吧？n=最短的一个string的长度，m=string个数。
: 没更简便的了吧？
: longest common substring:
: 这题的两种解法都要掌握吗？DP比较容易，但是时间复杂度要O(n1xn2)。suffix tree
: 时间复杂度是O(n1+n2)，但是貌似很复杂，很想放弃了。有经验的大牛们，这题需要掌
: 握suffix算法吗？

i*h2012-09-04 07:09

3 楼

suffix array is much easier to implement

j*22012-09-04 07:09

4 楼

DP用的就是suffix array吧？用generalized suffix tree是另一种，不过还是决定把
它搞搞清楚了。好像很多DP问题都可以用suffix tree来搞。

【在 i***h 的大作中提到】

: suffix array is much easier to implement

i*h2012-09-04 07:09

5 楼

DP和suffix array没什么直接关系吧

【在 j******2 的大作中提到】

: DP用的就是suffix array吧？用generalized suffix tree是另一种，不过还是决定把
: 它搞搞清楚了。好像很多DP问题都可以用suffix tree来搞。

j*22012-09-04 07:09

6 楼

我的意思是：longest common substring这个问题的DP解法就是用DP来算suffix array
的长度。

【在 i***h 的大作中提到】

: DP和suffix array没什么直接关系吧

i*h2012-09-04 07:09

7 楼

不用DP,
suffix array排序, 然后过一遍就行了

array

【在 j******2 的大作中提到】

: 我的意思是：longest common substring这个问题的DP解法就是用DP来算suffix array
: 的长度。

j*22012-09-04 07:09

8 楼

那个。。。过一遍，用到了前面的结果，不是就叫DP的吗？
还是我对DP的理解又错拉

【在 i***h 的大作中提到】

: 不用DP,
: suffix array排序, 然后过一遍就行了
:
: array

C*U2012-09-04 07:09

9 楼

你应该google一下suffix array及算法

【在 j******2 的大作中提到】

: 那个。。。过一遍，用到了前面的结果，不是就叫DP的吗？
: 还是我对DP的理解又错拉

j*22012-09-04 07:09

10 楼

看了下，好像不是很简单的啊，尽是些paper。。。
这个suffix array和suffix tree的linear算法要不要掌握啊？本来是在搞DP，结果被
这个longest common substring引得来看这个suffix tree/array，投入的时间越来越
多，但是150和leetcode上都没啥suffix tree/array的问题啊，只有个strstr还蛮简单
的。。。
不是科班出身的就是累啊，千疮百孔的。。。

【在 C***U 的大作中提到】

: 你应该google一下suffix array及算法

i*h2012-09-04 07:09

11 楼

直接狗这个题吧, 和DP没半毛钱关系

j*22012-09-04 07:09

12 楼

就是google出来wiki说用DP啊，
http://en.wikipedia.org/wiki/Longest_common_substring_problem

【在 i***h 的大作中提到】

: 直接狗这个题吧, 和DP没半毛钱关系

C*U2012-09-04 07:09

13 楼

是有些麻烦。。。。我觉得现场写不太可能把。
我的算法课的project就是做linear time suffix array construction + wavelet
tree 来实现string match
当然大牛可能有很简单的办法实现

【在 j******2 的大作中提到】

: 看了下，好像不是很简单的啊，尽是些paper。。。
: 这个suffix array和suffix tree的linear算法要不要掌握啊？本来是在搞DP，结果被
: 这个longest common substring引得来看这个suffix tree/array，投入的时间越来越
: 多，但是150和leetcode上都没啥suffix tree/array的问题啊，只有个strstr还蛮简单
: 的。。。
: 不是科班出身的就是累啊，千疮百孔的。。。

j*22012-09-04 07:09

14 楼

就是。还是暂时放弃算了。

【在 C***U 的大作中提到】

: 是有些麻烦。。。。我觉得现场写不太可能把。
: 我的算法课的project就是做linear time suffix array construction + wavelet
: tree 来实现string match
: 当然大牛可能有很简单的办法实现

i*h2012-09-04 07:09

15 楼

用C++ STL, 还好了
下面的代码少了最后一步, 也没有sanity check
但也不难
当然效率不是最好的
#include
#include
#include
#include
using namespace std;
bool
compstr(char* a, char* b)
{
return strcmp(a,b)<0;
}
void
suffixArray(char *a, char *b)
{
char *m = (a>b)? a-1 : b-1;
char* suffix[strlen(a)+strlen(b)];
for(int i = 0; isuffix[i] = a+i;
}
for(int i=0; isuffix[strlen(a)+i] = b+i;
}
sort(suffix, suffix+strlen(a)+strlen(b), compstr);
for(int i=0; iif( (suffix[i]-m)*(suffix[i+1]-m) < 0) {
// find common prefix of suffix[i] and suffix[i+1]
}
}
return;
}

j*22012-09-04 07:09

16 楼

谢谢好心的牛人。等我慢慢消化下。

【在 i***h 的大作中提到】

: 用C++ STL, 还好了
: 下面的代码少了最后一步, 也没有sanity check
: 但也不难
: 当然效率不是最好的
: #include
: #include
: #include
: #include
: using namespace std;
: bool