lcs.chpl

proc lcs(a: string, b: string): string {
  var lengths: [1..a.size+1, 1..b.size+1] int;
  for (i, x) in zip(1..a.size, a) {
    for (j, y) in zip(1..b.size, b) {
      if x == y {
        lengths[i+1, j+1] = lengths[i, j] + 1;
      } else {
        lengths[i+1, j+1] = max(lengths[i+1, j], lengths[i, j+1]);
      }
    }
  }

  var result = '';

  var x = a.size+1,
      y = b.size+1;

  while x != 1 && y != 1 {
    if lengths[x, y] == lengths[x-1, y] then x -= 1;
    else if lengths[x, y] == lengths[x, y-1] then y -= 1;
    else {
      assert(a[x-1] == b[y-1]);
      result = a[x-1] + result;
      x -= 1;
      y -= 1;
    }
  }
  return result;
}


writeln(lcs('1234', '1224533324')); // 1234


writeln(lcs('thisisatest', 'testing123testing')); // tsitest

TODO: Submit to https://rosettacode.org/wiki/Longest_common_subsequence