Day 133-Q4 | Levenshtein Automaton（レーベンシュタイン・オートマトン）

問題

テキスト$T$（長さ$N$）とパターン$P$（長さ$M$）、許容編集距離$K$が与えられる。$T$の部分文字列（開始・終了位置は自由）のうち、$P$との編集距離（挿入・削除・置換、各コスト1）が$K$以下であるものが存在するような終了位置$i$（$1$-indexed）の個数を求めよ。

これは「編集距離$\le K$で$P$を近似的に含む位置」を判定するレーベンシュタイン・オートマトンを$T$に対して走らせる問題であり、状態は「$P$の各prefixとの残差ベクトル」として表現できる。

入力形式

N M K
T
P

制約

$1 \le M \le 20$

$1 \le N \le 2\times10^5$

$0 \le K \le \min(3,M)$

$T,P$は英小文字のみ

入出力例

入力例1

2 1 0
ab
a

出力例1

入力例2

2 1 1
ab
a

出力例2

概念図

ヒント（段階的開示）

ヒント1（方向性）

「$T$のある部分文字列が$P$と編集距離$\le K$」を素朴に全部分文字列で判定すると$O(N^2)$。「開始位置が自由」という性質は、通常の編集距離DPの初期行を「全部0」にする（＝どこからでもコスト0で新しく部分文字列が始められる）ことで、1回の左から右へのスキャンだけで表現できる。

ヒント2（アプローチ）

$D[j]$を「$P[0..j)$を、現在位置までに読んだ$T$のある接尾辞に変換する最小編集回数（開始点は自由）」とする。$T$を1文字ずつ読みながら通常の編集距離DPと同じ漸化式で更新するが、毎回$D'[0]=0$にリセットする。$D[M]\le K$になった瞬間、その位置が条件を満たす終了位置。

ヒント3（誘導）

def count_matches(T, P, K):
    m = len(P)
    D = list(range(m + 1))
    count = 0
    for ch in T:
        newD = [0] * (m + 1)  # newD[0] = 0（新規開始を常に許可）
        for j in range(1, m + 1):
            cost_sub = D[j-1] + (0 if P[j-1]==ch else 1)
            cost_del = D[j] + 1
            cost_ins = newD[j-1] + 1
            newD[j] = min(cost_sub, cost_del, cost_ins)
        D = newD
        if D[m] <= K: count += 1
    return count

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1]); k = int(data[2])
    T = data[3].decode()
    P = data[4].decode()

    D = list(range(m + 1))
    count = 0
    for i in range(n):
        ch = T[i]
        newD = [0] * (m + 1)
        prev = D
        cur = newD
        for j in range(1, m + 1):
            cost_sub = prev[j - 1] + (0 if P[j - 1] == ch else 1)
            cost_del = prev[j] + 1
            cost_ins = cur[j - 1] + 1
            best = cost_sub
            if cost_del < best:
                best = cost_del
            if cost_ins < best:
                best = cost_ins
            cur[j] = best
        D = cur
        if D[m] <= k:
            count += 1

    print(count)

solve()

Step-by-Step 解説

1部分文字列マッチを行ベクトルDPに落とし込む
$T$側の初期条件を「どの位置からでもコスト0で新しい対応付けを始められる」ようにする。列方向のDPで$D'[0]$を毎回0にリセットすれば実現できる。

2行ベクトルの意味＝オートマトンの状態
$D[0..M]$は現在位置までに読んだ$T$の情報を「$P$の各prefixとの残差」に圧縮したもので、これがレーベンシュタイン・オートマトンの状態そのもの。

3なぜ帯だけで十分か
$D[j]$と対角成分$j$との差が$K$を超えている要素は、以降どう更新しても最小コストが$K$を下回れない。帯だけ保持すれば$O(NK)$に落ちる。

4計算量
帯を使わない実装でも$O(NM)$。$N\le2\times10^5,M\le20$で最大$4\times10^6$回、Pythonでも十分。

5応用範囲
Elasticsearch/LuceneのFuzzy Queryなど、あいまい検索の核となっている技術。

よくあるミス

ミス	原因	正しい書き方
newD[0]を前の値から更新してしまう	通常の編集距離DPの感覚のまま実装	部分文字列マッチでは毎回newD[0]=0に固定リセット
cost_insを前の行(D[j-1])から取ってしまう	挿入・削除の役割方向を取り違える	挿入=同じ行の1つ左(newD[j-1]+1)、削除=前の行の同じ列(D[j]+1)
バンド幅を無視して全区間計算のまま満足	帯だけ持てば十分という高速化ポイントを理解していない	N,Mが大きい場合は\|j-i\|≤Kの帯だけ更新するよう書き換える
「距離の最小値」と「距離≤Kの判定」を混同	本問は存在判定であることを見落とす	各終了位置iについてD[m]≤Kかどうかだけ判定しカウント

次のステップ

発展: バンド幅Kに限定した実装に書き換え、O(NK)に高速化して実行時間を比較せよ。
発展2: 複数パターンを同時にあいまい検索したい場合、Aho-Corasickのトライ構造と組み合わせ各ノードに残差ベクトルを伝播させる拡張を設計せよ。
次回予告: 次回のテーマは今後のセッションで選定

自己評価

完全理解おおむね理解要復習

Day 133-Q4 — Levenshtein Automaton（レーベンシュタイン・オートマトン）

問題