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

弱弱地问一下,除了KMP和朴素的算法还有别的什么来判断是否为一个子串么?

Posted by jianchenhao at 2006-12-08 21:25:26 on Problem 3080
In Reply To:KMP其实平均不好 Posted by:frkstyc at 2006-12-08 21:10:00

Followed by:

后缀数组....后缀树..... (0) wywcgs 2006-12-08 21:41:37
- sigh~~~目前只会写O(k*N^2)的后缀数组 (0) goodhorsezxj 2006-12-09 21:00:50
  - k是什么 n是什么? (0) sunmoonstar 2006-12-09 21:05:21
  - 那个O(n)的论文讲得貌似挺浅显易懂的…… (0) wywcgs 2006-12-09 21:28:01
    - 但是O(n)rmq pk O(nlogn)rmq 在n<100w的时候几乎没有优势 (0) sunmoonstar 2006-12-09 21:32:18
      - 那就O(nlgn)rmq - - (0) wywcgs 2006-12-09 21:33:47
      - O(n)的没写过... (0) ArXoR 2006-12-09 21:43:33
        写了,效果不好,空间复杂度也不小 (0) sunmoonstar 2006-12-10 00:19:12

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator