j******2
发帖数: 362 | 1 longest common prefix:
这题就只有O(n*m)的解法了吧？n=最短的一个string的长度，m=string个数。
没更简便的了吧？
longest common substring:
这题的两种解法都要掌握吗？DP比较容易，但是时间复杂度要O(n1xn2)。suffix tree
时间复杂度是O(n1+n2)，但是貌似很复杂，很想放弃了。有经验的大牛们，这题需要掌
握suffix算法吗？ |
j******2
发帖数: 362 | 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***h
发帖数: 12655 | 3 suffix array is much easier to implement |
j******2
发帖数: 362 | 4 DP用的就是suffix array吧？用generalized suffix tree是另一种，不过还是决定把
它搞搞清楚了。好像很多DP问题都可以用suffix tree来搞。
【在 i***h 的大作中提到】
: suffix array is much easier to implement
|
i***h
发帖数: 12655 | 5 DP和suffix array没什么直接关系吧
【在 j******2 的大作中提到】
: DP用的就是suffix array吧？用generalized suffix tree是另一种，不过还是决定把
: 它搞搞清楚了。好像很多DP问题都可以用suffix tree来搞。
|
j******2
发帖数: 362 | 6 我的意思是：longest common substring这个问题的DP解法就是用DP来算suffix array
的长度。
【在 i***h 的大作中提到】
: DP和suffix array没什么直接关系吧
|
i***h
发帖数: 12655 | 7 不用DP,
suffix array排序, 然后过一遍就行了
array
【在 j******2 的大作中提到】
: 我的意思是：longest common substring这个问题的DP解法就是用DP来算suffix array
: 的长度。
|
j******2
发帖数: 362 | 8 那个。。。过一遍，用到了前面的结果，不是就叫DP的吗？
还是我对DP的理解又错拉
【在 i***h 的大作中提到】
: 不用DP,
: suffix array排序, 然后过一遍就行了
:
: array
|
C***U
发帖数: 2406 | 9 你应该google一下suffix array及算法
【在 j******2 的大作中提到】
: 那个。。。过一遍，用到了前面的结果，不是就叫DP的吗？
: 还是我对DP的理解又错拉
|
j******2
发帖数: 362 | 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***h
发帖数: 12655 | |
j******2
发帖数: 362 | |
C***U
发帖数: 2406 | 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******2
发帖数: 362 | 14 就是。还是暂时放弃算了。
【在 C***U 的大作中提到】
: 是有些麻烦。。。。我觉得现场写不太可能把。
: 我的算法课的project就是做linear time suffix array construction + wavelet
: tree 来实现string match
: 当然大牛可能有很简单的 办法实现
|
i***h
发帖数: 12655 | 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; i
suffix[i] = a+i;
}
for(int i=0; i
suffix[strlen(a)+i] = b+i;
}
sort(suffix, suffix+strlen(a)+strlen(b), compstr);
for(int i=0; i
if( (suffix[i]-m)*(suffix[i+1]-m) < 0) {
// find common prefix of suffix[i] and suffix[i+1]
}
}
return;
} |
j******2
发帖数: 362 | 16 谢谢好心的牛人。等我慢慢消化下。
【在 i***h 的大作中提到】
: 用C++ STL, 还好了
: 下面的代码少了最后一步, 也没有sanity check
: 但也不难
: 当然效率不是最好的
: #include
: #include
: #include
: #include
: using namespace std;
: bool
|
