問題:それぞれサイズ n と m の 2 つの文字列について、O(mn) での自明な編集距離 DP の定式化と計算を知っています。しかし、編集距離 f の最小値のみを計算する必要があり、それが |f|<=s に制限されている場合、O(min(m,n) + s^2) で計算できることを最近知りました。または O(s*min(m,n)) [ウィキペディア] 時間。
これが DP ベースの場合、またはアルゴリズムを説明する場合は、その背後にある dp の定式化を説明してください。
リンクimproved algorithmのセクションを
見てください: http://en.wikipedia.org/wiki/Edit_distance .
改善された UKKONEN のアルゴリズムに関するもう 1 つのリンクhttp://www.berghel.net/publications/asm/asm.php
前もって感謝します。