Re: [問題] KMP
※ 引述《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
推
03/29 13:33, , 1F
03/29 13:33, 1F
推
03/29 13:44, , 2F
03/29 13:44, 2F