[理工] 106交大資聯資料結構

看板Grad-ProbAsk作者 (滷蛋)時間7年前 (2017/02/10 19:20), 7年前編輯推噓24(24推 0噓 50→)
留言74則, 20人參與, 最新討論串1/1
http://i.imgur.com/FutbAdY.jpg
這題大家會解嗎? 我第一個直覺是Master 下去解得 case3 但是那個bn真的讓人有點不舒服QQ 大大們怎麼解呢? 祝各位金榜題名 明天開戰台大 加油!!! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.105.39 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486725650.A.260.html ※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:21:21
→
02/10 19:25, , 1F
substitution
02/10 19:25, 1F
※ 編輯: 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
推
02/10 19:30, , 2F
b是非負常數，所以f(n)是O(n)
02/10 19:30, 2F
※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:32:49
→
02/10 19:36, , 3F
O(n^log_2(3)) 我最後算這樣(?
02/10 19:36, 3F
→
02/10 19:37, , 4F
我以為f(n)是O(1)最後我也寫O(n^log2(3))
02/10 19:37, 4F
推
02/10 19:38, , 5F
我帶master也是n^log_2(3)
02/10 19:38, 5F
推
02/10 19:38, , 6F
我直接帶master去解
02/10 19:38, 6F
靠邀我a和b放反了 我寫n^log_3(2) 幫QQ... ※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 19:40:09
→
02/10 19:39, , 7F
分數 2分 應該是用 master 就好 雖然我連兩題都用sub
02/10 19:39, 7F
推
02/10 19:55, , 8F
別說啦我紅黑樹root 化成紅色的QQ
02/10 19:55, 8F
→
02/10 19:55, , 9F
分數兩分他又說give，我把算式寫出來後就直接寫答案了
02/10 19:55, 9F
→
02/10 19:57, , 10F
雖然substitution應該也是短短的
02/10 19:57, 10F
推
02/10 20:01, , 11F
幫QQ 沒關係兩分而已 清大生成看錯 7分QQ
02/10 20:01, 11F
→
02/10 20:03, , 12F
借問一下第一題failure function，他給的定義跟我之前
02/10 20:03, 12F
→
02/10 20:04, , 13F
看到的不太一樣，之前看到的是f(j)=...，這個是另外一
02/10 20:04, 13F
→
02/10 20:04, , 14F
種嗎？
02/10 20:04, 14F
→
02/10 20:06, , 15F
有一個叫prefix function
02/10 20:06, 15F
第一題我看不懂他想問什麼QQQQQ ※ 編輯: jerry900287 (111.243.105.39), 02/10/2017 20:08:25
→
02/10 20:09, , 16F
兩種是指從0開始和從-1開始嗎 我只看過這兩個
02/10 20:09, 16F
推
02/10 20:10, , 17F
應該是這個@@
02/10 20:10, 17F
推
02/10 20:16, , 18F
第一題應該是KMP求failure function
02/10 20:16, 18F
推
02/10 20:21, , 19F
這是horowitz上寫的定義,印象中一模一樣
02/10 20:21, 19F
推
02/10 20:22, , 20F
可是他寫f(i)=The largest i < j...
02/10 20:22, 20F
→
02/10 20:22, , 21F
這樣f(4)不就是代表i永遠為4了嗎？
02/10 20:22, 21F
推
02/10 20:23, , 22F
我算f(4)=1, f(5)=2,f(6)=3,f(7)=-1, f(8)=0
02/10 20:23, 22F
→
02/10 20:23, , 23F
如果是f(j)=The largest i < j的話應該就是很常見的那
02/10 20:23, 23F
→
02/10 20:23, , 24F
種
02/10 20:23, 24F
→
02/10 20:24, , 25F
我也是照這樣算沒錯，只是覺得怪怪的
02/10 20:24, 25F
→
02/10 20:25, , 26F
不過我f(8)寫成1了XD應該是0沒錯
02/10 20:25, 26F
→
02/10 20:25, , 27F
我覺得是筆誤...我就不管他照算了...
02/10 20:25, 27F
→
02/10 20:26, , 28F
如果是筆誤就好了，怕是我搞錯
02/10 20:26, 28F
→
02/10 20:27, , 29F
交大有一年有偷改failure定義的記錄XD
02/10 20:27, 29F
→
02/10 20:28, , 30F
prefix function應該是從0開始，failure function從-1
02/10 20:28, 30F
→
02/10 20:28, , 31F
開始，這是我知道的
02/10 20:28, 31F
推
02/10 20:30, , 32F
這就不知道了 交大題目有時候真的很神奇xD
02/10 20:30, 32F
推
02/10 20:31, , 33F
我看到題目求failure function 還有-1 就直接下去算了
02/10 20:31, 33F
→
02/10 20:32, , 34F
他給的定義我也是看不太懂XD
02/10 20:32, 34F
推
02/10 20:42, , 35F
他的定義 不是常見的那種function
02/10 20:42, 35F
→
02/10 20:42, , 36F
他有個pi+1 != pj+1
02/10 20:42, 36F
→
02/10 20:43, , 37F
一般的failure function沒有這個
02/10 20:43, 37F
推
02/10 20:44, , 38F
感覺全部都是-1 定義很怪
02/10 20:44, 38F
→
02/10 20:45, , 39F
這題我預定我本來就會錯 整張寫得很趕
02/10 20:45, 39F
→
02/10 20:46, , 40F
嗯嗯，後面那個我也有注意到，可是我光看f(i)就想不透
02/10 20:46, 40F
→
02/10 20:47, , 41F
了，就用102年交大的那個方法直接算，然後就下一題了
02/10 20:47, 41F
推
02/10 20:47, , 42F
我是幫他訂正啦XDDD 應該要是f(j)
02/10 20:47, 42F
→
02/10 20:48, , 43F
整張寫得很趕+1，其實三科我都很趕QQ
02/10 20:48, 43F
→
02/10 20:48, , 44F
Y大 F(7) 寫多少 ? 照理所不可能 -1 直接 1 吧 ?
02/10 20:48, 44F
→
02/10 20:49, , 45F
說
02/10 20:49, 45F
→
02/10 20:51, , 46F
我是寫-1拉
02/10 20:51, 46F
→
02/10 20:52, , 47F
不過我重新考慮了一下Pi+1 =\= Pj+1這件事之後發現
02/10 20:52, 47F
→
02/10 20:52, , 48F
只有f(6)=3存活下來，其他都變-1了QQ
02/10 20:52, 48F
推
02/10 20:53, , 49F
我前面那個考完數學馬上跟朋友說數學出這題目隨便考
02/10 20:53, 49F
→
02/10 20:53, , 50F
都能上。我：………
02/10 20:53, 50F
→
02/10 20:54, , 51F
Y大這麼一說有點道理 慘
02/10 20:54, 51F
推
02/10 20:54, , 52F
我是猜f(i)為0～i跟 i+1～last之間共同字串的最大長度
02/10 20:54, 52F
推
02/10 20:55, , 53F
QQ 5分應該GG
02/10 20:55, 53F
→
02/10 20:55, , 54F
aa大和snoopy大是對的，剛剛翻了一下Horowitz，交大真
02/10 20:55, 54F
→
02/10 20:55, , 55F
的偷改定義了QQ
02/10 20:55, 55F
→
02/10 20:56, , 56F
往好的方向想，如果教授一個f(4)~f(8)一個給1分的話，
02/10 20:56, 56F
→
02/10 20:56, , 57F
還有兩分XD
02/10 20:56, 57F
推
02/10 20:57, , 58F
應該不會..教授要改這麼多考卷 早就越改越不爽了
02/10 20:57, 58F
→
02/10 20:59, , 59F
也是QQ看到-1不夠多的直接劃掉最快XD
02/10 20:59, 59F
推
02/10 21:04, , 60F
我晚上重看一次，跟yu大答案一樣
02/10 21:04, 60F
推
02/10 21:13, , 61F
我好像有f6跟f8活下來XD
02/10 21:13, 61F
→
02/10 21:14, , 62F
他是要求j還是最大長度QQ我寫j
02/10 21:14, 62F
→
02/10 21:15, , 63F
應該是j拉，可是P(0+1)=P(8+1)耶，應該會變-1？
02/10 21:15, 63F
→
02/10 21:39, , 64F
好吧 我不知道哪根筋不對寫 0 1
02/10 21:39, 64F
推
02/10 21:47, , 65F
我是找最後段 這樣 p(j+1)是空的 就永遠不會等於p(I+1)了X
02/10 21:47, 65F
→
02/10 21:47, , 66F
D
02/10 21:47, 66F
推
02/10 21:49, , 67F
哭 沒仔細看完敘述
02/10 21:49, 67F
推
02/10 22:01, , 68F
第一題在98交大資演也有考過喔~~
02/10 22:01, 68F
→
02/10 22:05, , 69F
Pi+1=/=Pj+1代表比對之prefix和suffix的下一個字元不可
02/10 22:05, 69F
→
02/10 22:05, , 70F
以相合
02/10 22:05, 70F
→
02/10 22:06, , 71F
我是寫f(6)=3 其他都是-1
02/10 22:06, 71F
→
02/10 22:11, , 72F
太陰險了吧
02/10 22:11, 72F
→
02/10 22:11, , 73F
嗯嗯感謝l大指出考古題年度，跟我現在在家算的一樣XD
02/10 22:11, 73F
→
02/11 16:21, , 74F
我也只能回算才算對,慘慘5分噴
02/11 16:21, 74F
‣ 更多 jerry900287 的文章
文章代碼(AID): #1OdQ8I9W (Grad-ProbAsk)