c**********x
发帖数: 32 | 1 Question:
There are 1000 distinct strings, each string is composed by the chars in{‘a
','b','c','d'}. And each string.Length()==30;
here's a function aims at calculating the overlap of two different strings；
int overlapNumber(string str1, string str2){...}
overlapNumber is the length of largest prefix of str2 which is contained by
str1(Not necessary the surfix of str1)
and what I want is to calculate all the overlapNumbers between every two
strings within this string sets.
Notice: overlap(str1,str2) is sometimes not equal to overlap(str2,str1).
=========================================================================
My Solution:
My solution is somehow straightforward:
I change a little bit of the KMP string match algorithm and calculate every
two strings within this sets.
This takes O(n^2)
=========================================================================
Any Da Shen has a better solution?
I'm thinking of using tries...will it help?
Thanks! |
c**********x
发帖数: 32 | |
c**********x
发帖数: 32 | 3 补充:
这题的优化只能在两两string的求overlap上面优化吗？有没有什么方法可以在整个
string set上面优化神马的？ |
z****s
发帖数: 409 | 4 想了一会没想出来。。。不过你这数据也太没诱惑力了，已经能1000^2*60做出来了，
实在没动力想了。 |
x*****a
发帖数: 9 | 5 优化overlapNumber+整体.
给每一个str做他的suffix tree. 然后就正常搜 |
s**********e
发帖数: 326 | 6
我也觉得应该是这样优化。
【在 x*****a 的大作中提到】
: 优化overlapNumber+整体.
: 给每一个str做他的suffix tree. 然后就正常搜
|
g*********e
发帖数: 14401 | 7 为什么你的solution只有n2时间？每对str的kmp运算不止常数时间吧？
‘a
by
【在 c**********x 的大作中提到】
: Question:
: There are 1000 distinct strings, each string is composed by the chars in{‘a
: ','b','c','d'}. And each string.Length()==30;
: here's a function aims at calculating the overlap of two different strings；
: int overlapNumber(string str1, string str2){...}
: overlapNumber is the length of largest prefix of str2 which is contained by
: str1(Not necessary the surfix of str1)
: and what I want is to calculate all the overlapNumbers between every two
: strings within this string sets.
: Notice: overlap(str1,str2) is sometimes not equal to overlap(str2,str1).
|
c**********x
发帖数: 32 | 8
嗯 应该是n^2 * n
【在 g*********e 的大作中提到】
: 为什么你的solution只有n2时间？每对str的kmp运算不止常数时间吧？
:
: ‘a
: by
|
c**********x
发帖数: 32 | 9
错了。。
是 n^2 * length
【在 g*********e 的大作中提到】
: 为什么你的solution只有n2时间？每对str的kmp运算不止常数时间吧？
:
: ‘a
: by
|
c**********x
发帖数: 32 | 10
弱弱的问一句，suffix tree怎么写啊？看了一晚上了。。。
【在 x*****a 的大作中提到】
: 优化overlapNumber+整体.
: 给每一个str做他的suffix tree. 然后就正常搜
|
C******w
发帖数: 23 | 11 用个简单的dp可以求得str1 str2的overlap，复杂度是O(length) |
