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