🐍

Rustで動的計画法の実装：LCS

2023/04/09に公開

Rust

AtCoder

動的計画法

tech

はじめに

動的計画法を実装してみて、Rustの勉強をやってみる。問題としてはEducational DP Contestという動的計画法の練習を目的としたコンテストのものを使用。

https://atcoder.jp/contests/dp/

AからZまで問題が設定されているが、今回はFのLCS（Longest-common subsequence problem）、日本語では最長共通部分列問題。そんなに難しい問題ではないが、問題としては「最長のものをひとつ求めてください。」つまり、復元をちゃんとしないといけない。

利用したライブラリ

chmaxは可変長引数をとれるものを利用。2つ以上のものと比較して一番大きな値に変更する。

標準入力からデータを読み取る部分はproconioを利用。今回文字列をVec(char)で読み込むために、proconio::marker::Charsも利用。

完成したコード

動的計画法の実装は $i, j$ のループ部分だけで、復元の方がコードが多くなってしまっている。

lcs.rs

use proconio::input;
use proconio::marker::Chars;

fn main(){
    input!(
        s: Chars,
        t: Chars,
    );
    
    let mut dp: Vec<Vec<i64>>  = vec![vec!(0; t.len() + 1); s.len() + 1];
    for i in 1..s.len() + 1 {
        for j in 1..t.len() + 1 {
            if s[i - 1] == t[j - 1] {
                chmax!(dp[i][j], dp[i-1][j-1] + 1, dp[i][j-1], dp[i-1][j-1]);
            } else {
                chmax!(dp[i][j], dp[i][j-1], dp[i-1][j]);
            }
        }
    }

    let (mut sp, mut tp) = (s.len(), t.len());
    let mut result: Vec<char> = Vec::new();
    if dp[sp][tp] > 0 {
        loop {
            if dp[sp][tp] == dp[sp - 1][tp - 1] + 1 && s[sp -1] == t[tp - 1] {
                sp -= 1; tp -= 1;
                result.push(s[sp]);
            } else if dp[sp][tp] == dp[sp - 1][tp] {
                sp -= 1;                
            } else if dp[sp][tp] == dp[sp][tp - 1] {
                tp -= 1;
            } else {
                println!("restoration error at ({}, {})", sp, tp);
                break;
            }
            if sp == 0 || tp == 0 { break; }
        }
        for i in result.iter().rev() {
            print!("{}", i);
        }
        println!("");
    } else {
        println!("");
    }
}

アルゴリズム

詳しい説明は検索すればでてくると思うが、文字列 $s$ の $i-1$ 文字目までと文字列 $t$ の $j-1$ 文字列までの最長共通部分列の長さをdp[i][j]に入れていく。
0-originとかを気をつければ間違えないはず。可変長引数を取れるchmaxを使うと綺麗に書ける。

復元処置

左斜め上dp[i-1][j-1]からの移動の時に部分列の長さが増えることを意識すればそこまで難しくはない。if文が並んでいる箇所は左辺が同じなのでmatchを使いたい気分になるが、これはパターンマッチではないので書けない。

このようには書けない

match dp[sp][tp] {
  dp[sp - 1][tp - 1] + 1 if s[sp -1] == t[tp - 1] => {
    sp -= 1; tp -= 1;
    result.push(s[sp]);
  }
  dp[sp - 1][tp] => {

後ろからマッチした文字をpopしていくと、resultには逆順に文字列が完成する。そのため、reverse iteratorを使って逆順に出力することで元の文字列を取得する。

lcs.rs

        for i in result.iter().rev() {
            print!("{}", i);
        }

共通部分列が存在しない場合は、空文字列を指定することになっているので、追加している。ここのif文はなくても正常に動作する。dpは全部0になっており、走査してもresultは空のままなので空文字列が出力される。このため、どちらかと言えば「見た目」のために記述している部分。

lcs.rs

    if dp[sp][tp] > 0 {
    
     } else {
        println!("");
    }

全ての結果を表示させる

問題文には「答えが複数ある場合、どれを出力してもよい。」とあるので、上記で問題ないが、「すべて出力する」時は全部のパスを探索する必要がある。以下のように再帰で書くのが自然だとは思う。

fn restoration(dp:&Vec<Vec<i32>>, s:&Vec<char>, t:&Vec<char>, sp_s:usize, tp_s:usize, result:&Vec<char>) {
    let (mut sp, mut tp) = (sp_s, tp_s);
    if sp == 0 || tp == 0 {
        for i in result.iter().rev() {
            print!("{}", i);
        }
        println!("");
    } else {
        loop {
            if dp[sp][tp] == dp[sp - 1][tp - 1] + 1 && s[sp - 1] == t[tp - 1] {
                let mut res = result.clone();
                res.push(s[sp - 1]);
                restoration(dp, s, t, sp - 1, tp - 1, &res);
            }
            if dp[sp][tp] == dp[sp - 1][tp] {
                sp -= 1;                
            } else if dp[sp_s][tp] == dp[sp_s][tp - 1] {
                    sp = sp_s;
                    tp -= 1;
            } else {
                break;
            }
        }
    }
}

呼び出しは以下のような感じ。複数のパスで同じ文字列ができる場合でもパス毎に表示してしまうので、本来はその対策も必要ではあるが、結果を集めて重複を削除するのが面倒だったのでそのままにしてある。

    let result: Vec<char> = Vec::new();
    restoration(&dp, &s, &t, s.len(), t.len(), &result);

Rustで動的計画法の実装：LCS

はじめに

利用したライブラリ

完成したコード

アルゴリズム

復元処置

全ての結果を表示させる

関連記事

Discussion