最適化アルゴリズムの課題完了

diffを作れと言う課題。LCS作るときにできるテーブルを利用して、右下から左上までのルートを求めて、逆流しながら異なってる部分を出力するという感じに実装してみた。

• テーブルの左上から、右下移動(マッチした部分での移動)が起こったところまで行く
• そこまでに右だけに移動してたら前回の参照位置からそこまでが参照ファイルに追加されてる
• 下だけに移動してたら入力ファイルで似たような削除が起こってる
• 両方移動してたらそれぞれの区間が変わってる
• そうじゃなかったら一致区間
• 右下移動が起こったところの次を、次の区間の先頭とする

こんな感じ。たぶんこの情報だけで実装できるのはCSだとawakiaくらいだと思うので問題なし。