Cod sursa(job #3370372)

Utilizator martinuke0Alexandru Martiniuc martinuke0 Data 25 octombrie 2026 19:36:54
Problema Cel mai lung subsir comun Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 1.59 kb
use std::fs;
use std::io::Write;

fn main() {
    let input = fs::read_to_string("cmlsc.in").expect("cannot read cmlsc.in");
    let mut tokens = input.split_whitespace().map(|t| t.parse::<usize>().unwrap());

    let m = tokens.next().unwrap();
    let n = tokens.next().unwrap();

    let a: Vec<usize> = (0..m).map(|_| tokens.next().unwrap()).collect();
    let b: Vec<usize> = (0..n).map(|_| tokens.next().unwrap()).collect();

    // dp[i][j] = LCS length of a[..i] and b[..j]
    // Use (m+1) x (n+1) table.
    let mut dp = vec![vec![0u16; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] + 1
            } else {
                dp[i - 1][j].max(dp[i][j - 1])
            };
        }
    }

    let lcs_len = dp[m][n] as usize;

    // Reconstruct one LCS by walking backwards.
    let mut result = Vec::with_capacity(lcs_len);
    let (mut i, mut j) = (m, n);
    while i > 0 && j > 0 {
        if a[i - 1] == b[j - 1] {
            result.push(a[i - 1]);
            i -= 1;
            j -= 1;
        } else if dp[i - 1][j] >= dp[i][j - 1] {
            i -= 1;
        } else {
            j -= 1;
        }
    }
    result.reverse();

    let mut out = String::new();
    out.push_str(&format!("{}\n", lcs_len));
    if lcs_len > 0 {
        let parts: Vec<String> = result.iter().map(|x| x.to_string()).collect();
        out.push_str(&parts.join(" "));
    }
    out.push('\n');

    let mut f = fs::File::create("cmlsc.out").expect("cannot create cmlsc.out");
    f.write_all(out.as_bytes()).expect("write failed");
}