本人预计明天Dow Jones明天涨1.8%个点，citi反弹极限值3.2%，不低于2%# Stock
l*8
1 楼
Give a string, calculate the numbers of distinct sub-string of it.
a*n
2 楼
顺便说一句：美股无论如何，也会跌到9200点的，在2个月之内
n*a
3 楼
这个题目可以用suffix tree做吗？
每个node纪录建tree的时候路过的次数，然后遍历找到所有次数为1的node
时间复杂度O(n^2)
每个node纪录建tree的时候路过的次数，然后遍历找到所有次数为1的node
时间复杂度O(n^2)
l*8
4 楼
恩，可能也就是O(n^2)了吧
【在 n******a 的大作中提到】
: 这个题目可以用suffix tree做吗？
: 每个node纪录建tree的时候路过的次数，然后遍历找到所有次数为1的node
: 时间复杂度O(n^2)
【在 n******a 的大作中提到】
: 这个题目可以用suffix tree做吗？
: 每个node纪录建tree的时候路过的次数，然后遍历找到所有次数为1的node
: 时间复杂度O(n^2)
r*7
5 楼
bruce force 也是O(n^2)啊
【在 l*********8 的大作中提到】
: 恩，可能也就是O(n^2)了吧
【在 l*********8 的大作中提到】
: 恩，可能也就是O(n^2)了吧
n*a
6 楼
brute force是n^3吧
【在 r****7 的大作中提到】
: bruce force 也是O(n^2)啊
【在 r****7 的大作中提到】
: bruce force 也是O(n^2)啊
n*a
7 楼
感觉不管怎么着也要是n^2了
望大牛赐教更好的做法
【在 l*********8 的大作中提到】
: 恩，可能也就是O(n^2)了吧
望大牛赐教更好的做法
【在 l*********8 的大作中提到】
: 恩，可能也就是O(n^2)了吧
e*m
8 楼
distinct substring的总数是O(n2),复杂度不可能小于 O(n2)
【在 n******a 的大作中提到】
: 感觉不管怎么着也要是n^2了
: 望大牛赐教更好的做法
【在 n******a 的大作中提到】
: 感觉不管怎么着也要是n^2了
: 望大牛赐教更好的做法
l*8
9 楼
是啊
【在 e***m 的大作中提到】
: distinct substring的总数是O(n2),复杂度不可能小于 O(n2)
【在 e***m 的大作中提到】
: distinct substring的总数是O(n2),复杂度不可能小于 O(n2)
g*y
10 楼
r*7
11 楼
一个极端的例子是，如果所有character都是不一样的，可以立即算出来是(n+1)*n/2
如果n^2直接遍历放hash table里不就行了
【在 l*********8 的大作中提到】
: 是啊
如果n^2直接遍历放hash table里不就行了
【在 l*********8 的大作中提到】
: 是啊
x*y
12 楼
It should be O(n) in suffix tree. It uses succinct format to do recording,
so even if there could be O(n^2) results, to get the number of distinct
substring, it's linear.
【在 n******a 的大作中提到】
: 这个题目可以用suffix tree做吗？
: 每个node纪录建tree的时候路过的次数，然后遍历找到所有次数为1的node
: 时间复杂度O(n^2)
so even if there could be O(n^2) results, to get the number of distinct
substring, it's linear.
【在 n******a 的大作中提到】
: 这个题目可以用suffix tree做吗？
: 每个node纪录建tree的时候路过的次数，然后遍历找到所有次数为1的node
: 时间复杂度O(n^2)
l*8
13 楼
刚才仔细看了一下，的确是挺好的方法。 谢谢:-)
【在 g**********y 的大作中提到】
: http://www.quora.com/Given-a-string-how-do-I-find-the-number-of
: 这个看上去是合理解
【在 g**********y 的大作中提到】
: http://www.quora.com/Given-a-string-how-do-I-find-the-number-of
: 这个看上去是合理解
l*8
14 楼
我觉得用suffix tree还是O(n^2)啊。 能否解释一下如何达到O(n) ?
,
【在 x***y 的大作中提到】
: It should be O(n) in suffix tree. It uses succinct format to do recording,
: so even if there could be O(n^2) results, to get the number of distinct
: substring, it's linear.
,
【在 x***y 的大作中提到】
: It should be O(n) in suffix tree. It uses succinct format to do recording,
: so even if there could be O(n^2) results, to get the number of distinct
: substring, it's linear.
相关阅读
FB 今天也亏了几大K古板以前卖pick的生意怎么没人做了？调低WB买入到卖出又一个倒在amzn的枪下了股版大牛觉得WYNN怎么样？#MeToo[通知] Stock 举办博彩：BA ER网易 NTES 基本面这个新闻让钢铁企业有一波大涨？[通知] Stock 举办博彩：黑庄 网易 ER我支持川普大赦180万非法移民，让他们成为公民 (转载)未来暴跌！nvda, nflx, amzn这三个泡沫那个先破。来个竞猜吧今天不抄底，明天抽自己？今年空NUGT/UGAZ亏了不少，还有人在空这俩货吗明天账户绿着的都是股神老衲也只能帮你们到这里了精荒了，前几天刚强行上车请板斧帮忙办了NTES[matta]每日股市小结 以及干货汇总(交易日每天更新)[通知] Stock 举办博彩：GOOG ER