import 'dart:math';

String lcsRecursion(String a, String b) {
  int aLen = a.length;
  int bLen = b.length;

  if (aLen == 0 || bLen == 0) {
    return "";
  } else if (a[aLen-1] == b[bLen-1]) {
    return lcsRecursion(a.substring(0,aLen-1),b.substring(0,bLen-1)) + a[aLen-1];
  } else {
    var x = lcsRecursion(a, b.substring(0,bLen-1));
    var y = lcsRecursion(a.substring(0,aLen-1), b);
    return (x.length > y.length)? x: y;
  }
}

String lcsDynamic(String a, String b) {
  var lengths = new List<List<int>>.generate(a.length + 1,
      (_) => new List.filled(b.length+1, 0), growable: false);