[理工] 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