LCS practice

main.rs

#![feature(unicode, str_char)]
#![allow(deprecated)]

fn max(l: usize, r: usize) -> usize {
  if l > r { l } else { r }
}

pub fn lcs(s0: &str, s1: &str) -> usize {
  let s0_tlen = s0.width(false);
  let s1_tlen = s1.width(false);
  let mut mm: Vec<Vec<usize>> = Vec::with_capacity(s0_tlen);
  let mut blank = Vec::with_capacity(s1_tlen);

  for _ in 0..s1_tlen + 1 { blank.push(0); }

  for _ in 0..s0_tlen + 1 { mm.push(blank.clone()); }

  for i in 1..s0_tlen + 1 {
    for j in 1..s1_tlen + 1 {
      if s0.char_at(i - 1) == s1.char_at(j - 1) {
        mm[i][j] = 1 + mm[i - 1][j - 1];
      } else {
        mm[i][j] = max(mm[i - 1][j], mm[i][j - 1]);
      }
    }
  }

  for v in mm.iter() {
    println!("{:?}", v);
  }

  mm[s0_tlen][s1_tlen]
}

#[test]
fn it_works() {
  assert_eq!(lcs("1234", "1224533324"), 4);
  assert_eq!(lcs("thisisatest", "testing123testing"), 7);
}