PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] KMP

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間12年前 (2012/03/28 22:32)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串1/1

※ 引述《wsx02 ()》之銘言： : 我想請問算failure function的問題 : 我在網路查到的寫法是 : 和(前一項的failure number + 1)項比較 : 相同的話 f = (前一項f + 1) : 不同的話 f = -1 <~~實際寫過是這邊出了問題 : 例子: : i 0 1 2 3 4 5 6 7 8 9 10 : p(i) a b z a b a b z a b z : f(i) -1 -1 -1 0 1 : i=4的算法: 和第(第3項的f + 1)項比較 = 和第(0 + 1)項比較 = 和第1項比較 : 第1項是b，和第4項的b相同，所以f(4) = f(3)+1 = 1 : i=5比出來是不同的 f(5)=-1 可是答案是f(5)=0 : 請問比出來不同的話 f(i)應該要怎麼寫呢? : 用這個方法有一個跑出來成功的例子 : i 0 1 2 3 4 5 6 7 8 9 : p(i) a b c a b c a c a b : f(i) -1 -1 -1 0 1 2 3 -1 0 1 : 謝謝你要先搞懂 f 的意義 f(i) 表示由 i 往前 f(i)+1 個字和字串開頭的 f(i)+1 個字相同 0 f(i) i | | | ↑ ↑ └────────────┘ 這兩個字串是一樣的因此你所謂的「拿 p(f(i-1)+1) 和 p(i) 比」就是在檢查這個字串能不能拉長如果不能的話並不能直接填 -1 因為有可能會出現這種情形: 0 f(i-1) i-1 | | | 雖然不等於但是這兩段相同 | 這裡才是正確的 f(i) 那要怎麼確定這件事呢? 其實我們再仔細觀察上圖會發現一件事: 這個字串其實是長這樣的: 0 f(i-1) i-1 | | | 其中 = | * 於是我們該做的是去找 p(*+1) 去和 p(i) 比那 * 是什麼? 再度觀察上圖就會發現: * = f(f(i-1)) ! 所以正確的做法是當比對 p(f(i-1)+1)≠p(i) 時下一個該比的是 p(f(f(i-1))+1) 和 p(i) 還不對就再取 f 一直到比對到 p(0) 和 p(i) 還是不一樣時才填 -1 進去 -- ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄ ▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄ ▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌ ▏ζ(▏●‵◥′●▊)Ψ ▏　　　　　　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄ █/|▊ 〃、〃▋ |\ ▎　　　　　　　ハルヒ主義　　　　　█▄▄▄█▄▄ ◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.91