Day 099-Q2 — Myers' Bit-Vector Algorithm（編集距離のビット並列高速化）

2026-07-22 赤色 Master / Phase 8+ ★★★★★★★★★ Myers' Bit-Vector Algorithm

問題

文字列 $S$（長さ $M$）と文字列 $T$（長さ $N$）が与えられる。$S$ を $T$ に一致させるために必要な、挿入・削除・置換（それぞれコスト1）の最小回数、すなわち 編集距離（レーベンシュタイン距離） を求めよ。

通常のDPでは $O(NM)$ かかるが、$M \le 60$ なら $S$ の各文字位置をビット列の1ビットに対応させ、1列分の更新を整数のビット演算だけで行う Myers' Bit-Vector Algorithm により全体 $O(N)$ で計算できる。

入力形式

S
T

制約

$1 \le M = |S| \le 60$
$1 \le N = |T| \le 2 \times 10^5$
$S, T$ は英小文字のみ

入出力例

入力例1

kitten
sitting

出力例1

3

入力例2

abcde
xxabcdexx

出力例2

4

概念図

DPの1列 → 整数1個のビット列に圧縮 通常のDP列（S="ab" の場合、行=Sの各文字, 縦にdpの値）: dp[0][j]=0 dp[1][j]=? dp[2][j]=? ←　この縦方向の差分パターンを 　　ビット列 Pv/Mv として表現 ビット表現（M=2bit の例、bit0=1文字目, bit1=2文字目）: 1 0 bit0 bit1 = Pv (1文字読むごとにAND/OR/XOR/+で更新) 文字を1つ読むたびに O(⌈M/64⌉) 回のビット演算だけで1列分を更新 → 全体 O(N)

ヒント（段階的開示）

ヒント1: 方向性
各 $j$ ごとに、直前の列から現在の列を計算する際の「1つ上のセルとの差分（+1, 0, -1）」のパターンには規則性がある。この差分パターンをビット列として持てば、1列全体の更新をまとめて処理できないか考えよ。
ヒント2: アプローチ
列方向の差分を「+1のビット集合 Ph」「−1のビット集合 Mh」、行方向を Pv, Mv として表現する。文字 $c$ ごとに前計算したビットマスク Peq[c]（$S$のどの位置と一致するか）を使うと、1文字読むたびの更新式がすべてビット演算の組み合わせで書ける。行末のビットが Ph に立てば score += 1、Mh に立てば score -= 1。
ヒント3: 誘導（コード骨格） 
def myers_edit_distance(s, t):
    m = len(s)
    MASK = (1 << m) - 1
    peq = {}
    for i, ch in enumerate(s):
        peq[ch] = peq.get(ch, 0) | (1 << i)

    Pv = MASK
    Mv = 0
    score = m
    topbit = 1 << (m - 1)
    for ch in t:
        eq = peq.get(ch, 0)
        # Xv, Xh, Ph, Mh をビット演算で計算し、score を更新
        ...
    return score

~（NOT）演算はPythonでは符号なし固定長ビットとして扱えないため、MASK ^ x で代用する。

模範解答 (Python)

import sys


def myers_edit_distance(s, t):
    m = len(s)
    if m == 0:
        return len(t)
    MASK = (1 << m) - 1
    peq = {}
    for i, ch in enumerate(s):
        peq[ch] = peq.get(ch, 0) | (1 << i)

    Pv = MASK
    Mv = 0
    score = m
    topbit = 1 << (m - 1)

    for ch in t:
        eq = peq.get(ch, 0)
        Xv = (eq | Mv) & MASK
        Xh = ((((eq & Pv) + Pv) & MASK) ^ Pv) | eq
        Xh &= MASK
        Ph = (Mv | (MASK ^ (Xh | Pv))) & MASK
        Mh = Pv & Xh & MASK

        if Ph & topbit:
            score += 1
        elif Mh & topbit:
            score -= 1

        Ph = ((Ph << 1) | 1) & MASK
        Mh = (Mh << 1) & MASK
        Pv = (Mh | (MASK ^ (Xv | Ph))) & MASK
        Mv = Ph & Xv & MASK

    return score


def solve():
    data = sys.stdin.read().split()
    s, t = data[0], data[1]
    print(myers_edit_distance(s, t))


solve()
計算量: $M \le 64$ なら1ワードに収まるため $O(N)$。$M > 64$ の場合はブロック分割で $O(N\lceil M/64\rceil)$。

Step-by-Step 解説

1前処理 Peq
$S$の各文字位置に対応するビットマスクPeq[c]を文字ごとに事前計算する。
2初期状態
dp[i][0]=iに対応させ、Pvを全ビット1、Mvを0、score=mに初期化する。
31文字ごとの更新式
Xh=(((eq&Pv)+Pv)^Pv)|eqの加算演算が核心で、一致が続く区間の右端を一括検出する（Myers, 1999）。
4scoreの更新と行方向への反映
Ph/Mhの末尾ビットでscoreを増減し、シフトして次列用のPv,Mvを作る。
5計算量とワード分割
$M\le64$なら1ワードで$O(N)$。$M>64$はブロック間キャリー伝播が必要で$O(N\lceil M/64\rceil)$。

よくあるミス

ミス原因正しい書き方
~xをそのまま使うPythonの~は無限桁2の補数を返し有限幅の式が壊れるMASK ^ xで$M$ビット幅のNOTを表現
Phシフト後に最下位ビットへの1立てを忘れるdp[0][j]=jの境界条件が反映されないPh = ((Ph << 1) | 1) & MASK
Xhの加算後にMASKでマスクし忘れる多倍長intの繰り上がりが以降の演算を汚染加算・シフトのたびに& MASKで切り詰める
$M>64$にも単一ワード実装を使う単一ワード実装はワード幅を前提ワード分割しブロックごとにキャリーを伝播

次のステップ

  • 発展: $M>64$対応の複数ワード版、または自由開始版（近似文字列検索・agrep）
  • 次回予告: MST検証アルゴリズム（全方位木DPによる最大辺クエリ・Komlós法の実用実装）

自己評価

自分の回答

気づき・メモ