※ 引述《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