Fw: [問題] KMP字串比對
看板Prob_Solve (計算數學 Problem Solving)作者honoYang (......)時間12年前 (2012/09/04 23:37)推噓1(1推 0噓 1→)留言2則, 2人參與討論串1/1
※ [本文轉錄自 C_and_CPP 看板 #1GHXQS8y ]
作者: honoYang (......) 看板: C_and_CPP
標題: [問題] KMP字串比對
時間: Tue Sep 4 22:56:25 2012
不好意思
因為有一個一直想不通的地方 所以來請教各位
我想借用一下這個連結的說明
http://w.csie.org/~b99902112/NTUcourse/Chapter8-String.pdf
在這個PDF檔的第3頁有說明KMP的演算法
而且我也參考了一本資料結構的書籍
但是一直不懂為什麼第3頁裡說的
（2） T[i+1]≠T[π[i]+1]：這時候就較麻煩一點，但你仔細觀察後會發現，既然T[i+1]
≠T[π[i]+1]，那下一個可能的匹配位置一定是T[π[π[i]+1]
為什麼T[i+1]≠T[π[i]+1]時 下一個匹配的位置一定是T[π[π[i]+1]
這個關聯性怎麼產生的
我實做了例子試驗的確是正確的
但自己無法合理解釋這件事
謝謝大家
--
請大家在2012年軍閥大選時
務必投我一票
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.240.32
→
09/04 23:16, , 1F
09/04 23:16, 1F
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: honoYang (114.43.240.32), 時間: 09/04/2012 23:37:39
推
09/05 00:40, , 2F
09/05 00:40, 2F
→
09/05 15:05, , 3F
09/05 15:05, 3F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
