Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

made好不容易写了个O(n)的suffix tree，结果还超内存，本来java用内存就比较大，能不能内存方面也给点优惠阿！

Posted by Iambitious at 2006-05-09 17:36:15 on Problem 2774

Followed by:

pf您写O(n)的suf tree.不过suf tree的内存就是要比suf array大些吧，印象中最好的内存也要16n/3.不过hqm说有种办法可以用k倍的时间换sqrt(k)的空间....不知道有谁看过类似的论文么？ (0) palmtenor 2006-05-09 21:26:17
- Re:pf您写O(n)的suf tree.不过suf tree的内存就是要比suf array大些吧，印象中最好的内存也要16n/3.不过hqm说有种办法可以用k倍的时间换sqrt(k)的空间....不知道有谁看过类似的论文么？ (74) Iambitious 2006-05-10 13:16:44
  - 那个三分的方法中有介绍这种tradeoff...这程序整了我一个晚上加一个上午..faint. (78) achilles 2006-05-24 13:31:16
感觉stree没那么短吧，而且还是java…… (0) frkstyc 2006-05-09 21:35:42
- Re:感觉stree没那么短吧，而且还是java…… (12) Iambitious 2006-05-10 13:00:39
  - 你的超了9M左右，所以不放了，再想办法吧 (16) frkstyc 2006-05-10 13:19:04
    - 那个70几M怎么过的? (0) xfxyjwf 2006-05-10 13:21:05
      - 不搞一下我怎么知道超9M？ (0) frkstyc 2006-05-10 13:21:30
    - Re:你的超了9M左右，所以不放了，再想办法吧 (66) Iambitious 2006-05-10 15:47:54
    - 我认为没必要在内存上限制，正式比赛也基本不限制内存 (35) hawk 2006-05-11 13:32:26
      - 那就加吧，弄个suffix tree不容易 (41) frkstyc 2006-05-11 13:35:16
        Re:那就加吧，弄个suffix tree不容易 (28) Iambitious 2006-05-11 18:51:04
        不过老是等别人放宽限制是不好的…… (32) frkstyc 2006-05-11 18:52:38
        内存本来就不该卡 (0) TN 2006-05-11 20:29:54
        不过64M足够的…… (0) frkstyc 2006-05-11 20:31:30
        如果不用Scanner的话说不定就已经过了 (32) frkstyc 2006-05-11 18:53:30
        Re:如果不用Scanner的话说不定就已经过了 (39) Iambitious 2006-05-11 18:56:02
        1216858 00448264 2774 Accepted 65712K 6134MS Java 2.83K 2006-05-11 18:58:39.0 (43) frkstyc 2006-05-11 18:59:06
        刚好能过的 (43) frkstyc 2006-05-11 18:59:15
搬来小板凳看大牛们讨论~~ (0) cryer 2006-05-10 17:55:30

Post your reply here:

Home Page Go Back To top