[理工] 106交大資演 AAQ8 PTT批踢踢實業坊

[理工] 106交大資演

作者: AAQ8 (不要就是要) 2019-01-14 15:40:19

https://i.imgur.com/QfGmcPL.jpg
想請問第一題要求什麼
看完題目完全沒頭緒

作者: godskull1535 (骷骷) 2019-01-14 15:48:00

演算法第三章KMP

作者: wei12f8158 (WEI) 2019-01-14 16:04:00

kmp的問題可以看這影片，講的很詳細https://youtu.be/GTJr8OvyEVQ

作者: AAQ8 (不要就是要) 2019-01-14 16:21:00

懂了想請問答案是f(4)=1,f(5)=2,f(6)=3,f(7)=-1,f(8)=0這樣嗎

作者: zaq851017 (BJ4) 2019-01-14 16:26:00

這題跟一般kmp不一樣哦

作者: a66862439 (柳橙) 2019-01-14 16:32:00

立宇講義寫說這題定義有誤!?

作者: wei12f8158 (WEI) 2019-01-14 16:56:00

些微不一樣，因為failure function的陣列是從0開始（prefix function是從1開始）所以初始條件f[0]=-1（簡單的記法就是prefix function算出來的值全部-1就是failure function了）https://i.imgur.com/UFXvYvV.jpg

作者: skyHuan (Huan) 2019-01-14 17:13:00

答案好像是f(6)=3其他都是-1耶看別人討論的，我也不會這題希望有高手解答QQ

作者: zaq851017 (BJ4) 2019-01-14 17:24:00

如果按照題意答案是樓上那樣子因為他有多那行 pi+1 != pj+1但這樣子這個答案就根本不是failure function了

作者: HungDa (hongren) 2019-01-14 17:57:00

其實要寫failure function,但是在考場看到亂定義頭一定很痛

作者: sdfg014025xx (隨便就好) 2019-01-14 19:09:00

所以這題是要照題意的function嗎

作者: nchuAM37 (應數37) 2019-01-14 22:12:00

我照題目算出來都是-1 所以這題答案是什麼？

作者: jojoboy0115 (jojo) 2019-01-15 00:29:00

推二樓大大，我也是看這影片才學會導出failure function!可是不知道原理@@

作者: MumiMumi5566 (姆咪56) 2019-01-17 19:54:00

如果把題目定義f(i)=xxx改成f(j)的話，就可以得出f(6)=3,其餘=-1的答案了，所以應該是題目ij打錯(?

繼續閱讀

[理工] 107清大（2-3-4）！Aa841018 線性代數內積kaidi620 [理工] 105中央計組sooge [理工] 105 清大計系 8dumpling1234 [理工] 106清大計科AVL treeparalyzation [理工] 102台大計科3.4題st474ddr [理工] 107 中山電波電子學答案討論pochen9 [理工] 106中央資結AAQ8 [理工] 104中正Huffman，第28題mohuan520 [理工] 104交大 OS(4)jojoboy0115