作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 106交大資演
時間Mon Jan 14 15:40:19 2019
https://i.imgur.com/QfGmcPL.jpg
想請問第一題要求什麼
看完題目完全沒頭緒
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.38.187
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547451622.A.CBC.html
1F：推 godskull1535: 演算法第三章KMP 01/14 15:48
2F：推 wei12f8158: kmp的問題可以看這影片，講的很詳細 01/14 16:04
4F：→ AAQ8: 懂了 想請問答案是f(4)=1,f(5)=2,f(6)=3,f(7)=-1,f(8)=0這 01/14 16:21
5F：→ AAQ8: 樣嗎 01/14 16:21
6F：推 zaq851017: 這題跟一般kmp不一樣哦 01/14 16:26
7F：推 a66862439: 立宇講義寫說這題定義有誤!? 01/14 16:32
8F：推 wei12f8158: 些微不一樣，因為failure function的陣列是從0開始（p 01/14 16:56
9F：→ wei12f8158: refix function是從1開始） 01/14 16:56
10F：推 wei12f8158: 所以初始條件f[0]=-1（簡單的記法就是prefix function 01/14 17:00
11F：→ wei12f8158: 算出來的值全部-1就是failure function了） 01/14 17:00
13F：推 skyHuan: 答案好像是f(6)=3其他都是-1耶 01/14 17:13
14F：→ skyHuan: 看別人討論的，我也不會這題希望有高手解答QQ 01/14 17:13
15F：推 zaq851017: 如果按照題意答案是樓上那樣子 01/14 17:24
16F：→ zaq851017: 因為他有多那行 pi+1 != pj+1 01/14 17:25
17F：→ zaq851017: 但這樣子這個答案就根本不是failure function了 01/14 17:26
18F：推 HungDa: 其實要寫failure function,但是在考場看到亂定義頭一定很 01/14 17:57
19F：→ HungDa: 痛 01/14 17:58
20F：推 sdfg014025xx: 所以這題是要照題意的function嗎 01/14 19:09
21F：推 nchuAM37: 我照題目算出來都是-1 所以這題答案是什麼？ 01/14 22:12
22F：推 jojoboy0115: 推二樓大大，我也是看這影片才學會導出failure funct 01/15 00:29
23F：→ jojoboy0115: ion!可是不知道原理@@ 01/15 00:29
24F：→ MumiMumi5566: 如果把題目定義f(i)=xxx改成f(j)的話，就可以得出f( 01/17 19:54
25F：→ MumiMumi5566: 6)=3,其餘=-1的答案了，所以應該是題目ij打錯(? 01/17 19:54