O(NP)アルゴリズム

あんまり真面目に受け止めないで

大まかな考え方

以下は「みじんこ」と「にんじん」の差分を検出する流れを書く

「みじんこ」から文字を削除・挿入して「にんじん」にしていく体で考える

差分検出を考える際に必要不可欠な「エディットグラフ」という図を書きながら考えていく

エディットグラフを書いてみる

https://gyazo.com/c9373817084a33f6f0ed5618ba386ea0

書いてみたのがこれ（唐突）

横軸の上に「みじんこ」、縦軸の横に「にんじん」と書いてある

元の文を横軸に、変更後の文を縦軸に書いている

縦横で同じ文字があるマスには斜めの線を引く

エディットグラフに線を引いてみる

こんな表を書いて何ができるかというと、「みじんこ」から文字を削除・挿入して「にんじん」にする最短の手順がわかるようになる

上で作った表に、左上から右下までを通る線を引く

この時、通過する交点の数は最小限に抑える

https://gyazo.com/a207300a5339e7093d5edef626fcd637

上の図を見ると、赤・青・黒の3種類の線で引かれているのがわかる

横線を赤、縦線を青、斜め線を黒で引いている

それぞれこういった意味がある

赤：上に書かれた文字を削除

青：左に書かれた文字を挿入

黒：同じ文字なので何もしない

つまり、上の表通りの文字操作をすれば、最短手順で「みじんこ」を「にんじん」にすることができる

一応、具体的にどのような操作をしているのかも書いておく

1. みじんこ

2. じんこ（「み」を削除）

3. にじんこ（「に」を挿入）

4. にんじんこ（「ん」を挿入）

5. にんじんこ（何もしない）

6. にんじんこ（何もしない）

7. にんじん（「こ」を削除）

最短の手順を見つけ出す

（そのうち書くかも）

要点

通った斜め線が多いほど最短手順になる

参考