KMPの失敗機能

Question

私はKMPの失敗関数fについて質問します。パターンの大きさはqが8より大きいか等しいと仮定します。

f（m/2）とf（3m/4）の値は、 4）= 0、f（m）= 3m/4であるか？

どのような戦略を実行する必要がありますか？私はKMPアルゴリズムを多かれ少なかれ取得すると思うが、私はここで考える方法を見つけることができません。どんなヒントもありがとうございます。

Answer 1

f（m）= 3m/4であることがわかります。したがって、{m/4; m}に属するiを有するf（i）は、i-m/4（0と3m/4の間のすべての自然数）に等しくなければならない。 f（m/2）= m/4（m/4 = m/2-m/4なので）、f（3m/4）= m/2（m/2 = 3m/4 -m/4）