→ ken52011219: substitution 02/10 19:25
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:25:53
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:26:27
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:27:20
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:28:43
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:29:15
推 gary19941208: b是非負常數，所以f(n)是O(n) 02/10 19:30
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:32:49
→ ken52011219: O(n^log_2(3)) 我最後算這樣(? 02/10 19:36
→ sickle30: 我以為f(n)是O(1)最後我也寫O(n^log2(3)) 02/10 19:37
推 s82901: 我帶master也是n^log_2(3) 02/10 19:38
推 lion83395: 我直接帶master去解 02/10 19:38
靠邀我a和b放反了 我寫n^log_3(2) 幫QQ...
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:40:09
→ ken52011219: 分數 2分 應該是用 master 就好 雖然我連兩題都用sub 02/10 19:39
推 leoone: 別說啦我紅黑樹root 化成紅色的QQ 02/10 19:55
→ yupog2003: 分數兩分他又說give，我把算式寫出來後就直接寫答案了 02/10 19:55
→ yupog2003: 雖然substitution應該也是短短的 02/10 19:57
推 AucK: 幫QQ 沒關係兩分而已 清大生成看錯 7分QQ 02/10 20:01
→ yupog2003: 借問一下第一題failure function，他給的定義跟我之前 02/10 20:03
→ yupog2003: 看到的不太一樣，之前看到的是f(j)=...，這個是另外一 02/10 20:04
→ yupog2003: 種嗎？ 02/10 20:04
→ a15151616: 有一個叫prefix function 02/10 20:06
第一題我看不懂他想問什麼QQQQQ
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 20:08:25
→ lion83395: 兩種是指從0開始和從-1開始嗎 我只看過這兩個 02/10 20:09
推 TWkobe: 第一題應該是KMP求failure function 02/10 20:16
推 krusnoopy: 這是horowitz上寫的定義,印象中一模一樣 02/10 20:21
推 yupog2003: 可是他寫f(i)=The largest i < j... 02/10 20:22
→ yupog2003: 這樣f(4)不就是代表i永遠為4了嗎？ 02/10 20:22
推 TWkobe: 我算f(4)=1, f(5)=2,f(6)=3,f(7)=-1, f(8)=0 02/10 20:23
→ yupog2003: 如果是f(j)=The largest i < j的話應該就是很常見的那 02/10 20:23
→ yupog2003: 種 02/10 20:23
→ yupog2003: 我也是照這樣算沒錯，只是覺得怪怪的 02/10 20:24
→ yupog2003: 不過我f(8)寫成1了XD應該是0沒錯 02/10 20:25
→ TWkobe: 我覺得是筆誤...我就不管他照算了... 02/10 20:25
→ yupog2003: 如果是筆誤就好了，怕是我搞錯 02/10 20:26
→ krusnoopy: 交大有一年有偷改failure定義的記錄XD 02/10 20:27
→ yupog2003: prefix function應該是從0開始，failure function從-1 02/10 20:28
→ yupog2003: 開始，這是我知道的 02/10 20:28
推 TWkobe: 這就不知道了 交大題目有時候真的很神奇xD 02/10 20:30
推 lion83395: 我看到題目求failure function 還有-1 就直接下去算了 02/10 20:31
→ lion83395: 他給的定義我也是看不太懂XD 02/10 20:32
推 aa06697: 他的定義 不是常見的那種function 02/10 20:42
→ aa06697: 他有個pi+1 != pj+1 02/10 20:42
→ aa06697: 一般的failure function沒有這個 02/10 20:43
推 endinfierce: 感覺全部都是-1 定義很怪 02/10 20:44
→ ken52011219: 這題我預定我本來就會錯 整張寫得很趕 02/10 20:45
→ yupog2003: 嗯嗯，後面那個我也有注意到，可是我光看f(i)就想不透 02/10 20:46
→ yupog2003: 了，就用102年交大的那個方法直接算，然後就下一題了 02/10 20:47
推 aa06697: 我是幫他訂正啦XDDD 應該要是f(j) 02/10 20:47
→ yupog2003: 整張寫得很趕+1，其實三科我都很趕QQ 02/10 20:48
→ ken52011219: Y大 F(7) 寫多少 ? 照理所不可能 -1 直接 1 吧 ? 02/10 20:48
→ ken52011219: 說 02/10 20:49
→ yupog2003: 我是寫-1拉 02/10 20:51
→ yupog2003: 不過我重新考慮了一下Pi+1 =\= Pj+1這件事之後發現 02/10 20:52
→ yupog2003: 只有f(6)=3存活下來，其他都變-1了QQ 02/10 20:52
推 joy7658x348: 我前面那個考完數學馬上跟朋友說數學出這題目隨便考 02/10 20:53
→ joy7658x348: 都能上。我：……… 02/10 20:53
→ darren0831: Y大這麼一說有點道理 慘 02/10 20:54
推 HEroKuma: 我是猜f(i)為0～i跟 i+1～last之間共同字串的最大長度 02/10 20:54
推 TWkobe: QQ 5分應該GG 02/10 20:55
→ yupog2003: aa大和snoopy大是對的，剛剛翻了一下Horowitz，交大真 02/10 20:55
→ yupog2003: 的偷改定義了QQ 02/10 20:55
→ yupog2003: 往好的方向想，如果教授一個f(4)~f(8)一個給1分的話， 02/10 20:56
→ yupog2003: 還有兩分XD 02/10 20:56
推 TWkobe: 應該不會..教授要改這麼多考卷 早就越改越不爽了 02/10 20:57
→ yupog2003: 也是QQ看到-1不夠多的直接劃掉最快XD 02/10 20:59
推 k2shouai: 我晚上重看一次，跟yu大答案一樣 02/10 21:04
推 leoone: 我好像有f6跟f8活下來XD 02/10 21:13
→ leoone: 他是要求j還是最大長度QQ我寫j 02/10 21:14
→ yupog2003: 應該是j拉，可是P(0+1)=P(8+1)耶，應該會變-1？ 02/10 21:15
→ ken52011219: 好吧 我不知道哪根筋不對寫 0 1 02/10 21:39
推 leoone: 我是找最後段 這樣 p(j+1)是空的 就永遠不會等於p(I+1)了X 02/10 21:47
→ leoone: D 02/10 21:47
推 a15151616: 哭 沒仔細看完敘述 02/10 21:49
推 lskdream: 第一題在98交大資演也有考過喔~~ 02/10 22:01
→ lskdream: Pi+1=/=Pj+1代表比對之prefix和suffix的下一個字元不可 02/10 22:05
→ lskdream: 以相合 02/10 22:05
→ lskdream: 我是寫f(6)=3 其他都是-1 02/10 22:06
→ sickle30: 太陰險了吧 02/10 22:11
→ yupog2003: 嗯嗯感謝l大指出考古題年度，跟我現在在家算的一樣XD 02/10 22:11
→ hibiscus520: 我也只能回算才算對,慘慘5分噴 02/11 16:21