[理工] 96 清大資工failure function

看板Grad-ProbAsk作者 (小魯米)時間14年前 (2012/01/15 15:32), 編輯推噓3(3推 0噓 21→)
留言24則, 5人參與, 最新討論串1/1
1.compute the failure function f of the following string: P[1..8]="ABABABCA" 請問各位的解法是? 我自己寫的根網路上面解答提供的有點不太一樣 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.115.75.25
推
01/15 17:18, , 1F
-1, -1, 0, 1, 2, 3, -1, 0 ?
01/15 17:18, 1F
→
01/15 17:30, , 2F
依照KMP-algo應該是這答案,但是rnbjacky跟sos提供的答案
01/15 17:30, 2F
→
01/15 17:31, , 3F
是0 0 1 2 3 4 0 1
01/15 17:31, 3F
→
01/15 17:44, , 4F
樓上的才是正解
01/15 17:44, 4F
→
01/15 17:48, , 5F
其實這是一個初始值上設定的問題,我翻Horowitz的書是給-1
01/15 17:48, 5F
→
01/15 17:49, , 6F
但是我想會有兩個答案同時 給這個答案應該是有其他想法
01/15 17:49, 6F
→
01/15 17:50, , 7F
網路上面有少部分初始值給0,這考卷既沒給程式碼,又不給初值
01/15 17:50, 7F
→
01/15 17:51, , 8F
我不知道該怎麼寫答案,誰可以給我個明燈
01/15 17:51, 8F
→
01/15 18:15, , 9F
你去看一下比對的code，就知道初值該設啥了
01/15 18:15, 9F
→
01/15 18:19, , 10F
我就是看Horowitz書上的code阿
01/15 18:19, 10F
→
01/15 18:20, , 11F
那你可以跟我稍微解釋一下 你設初值=0的想法嗎@@
01/15 18:20, 11F
→
01/15 18:20, , 12F
還是我看的版本太舊了XD
01/15 18:20, 12F
→
01/15 18:21, , 13F
你看一下code裡有posp = failure[pos-1]+1
01/15 18:21, 13F
→
01/15 18:21, , 14F
題目的string的index從1開始
01/15 18:21, 14F
→
01/15 18:21, , 15F
如果設-1會跑到0
01/15 18:21, 15F
→
01/15 18:23, , 16F
我是這樣想的，可以討論一下
01/15 18:23, 16F
→
01/15 18:28, , 17F
恩 我想我應該了解了..ok 多謝
01/15 18:28, 17F
推
01/15 23:01, , 18F
Corman書上是從0開始 KMP我想還是照Corman巴
01/15 23:01, 18F
→
01/15 23:02, , 19F
你string從1開始就是1樓的
01/15 23:02, 19F
→
01/15 23:03, , 20F
講相反了= = corman是從1開始 所以沒有match到就是0
01/15 23:03, 20F
→
01/15 23:03, , 21F
從0開始就是1樓的
01/15 23:03, 21F
→
01/15 23:04, , 22F
KMP大部分應該都是從Corman上面出來的
01/15 23:04, 22F
推
01/15 23:16, , 23F
其實也不用你看到他P index從1開始你就知道要設0
01/15 23:16, 23F
→
09/11 14:46, , 24F
其實也不用你看到他P https://daxiv.com
09/11 14:46, 24F
‣ 更多 gskman 的文章
文章代碼(AID): #1F4e4c5Z (Grad-ProbAsk)