作者ajnightmare (阿华田)
看板NTUBIME100HW
标题[演算] slide 7,8 (05/01) 的待解决问题
时间Fri May 1 22:37:34 2009
1.string matching
(1)叙述问题
(2)解决方法
a.naive的方法 O(|S|*|P|)
b.Dan Gusfield's方法 O(|S|+|P|)
甚麽是Z value, 左护法, 右护法
计算Z value的方法
(3)时间复杂度解释
(4)正确性证明
找出Z value等於解决问题
case 1, 2, 3的证明
2.segment inetersection
(1)严谨地叙述问题和基本定义
(2)解决方法
a.naive的方法 O(n^2)
b.clever的方法 O(n*log(n))
(3)时间复杂度解释
(4)正确性证明
string matching感觉比较难
我先尝试2.(3), (4)
其他大家推文认领
上面讲得不详细的地方请补足
因为今天时间不太够
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 58.114.209.65