Index: common/diff.php
===================================================================
--- common/diff.php	(revision 1005)
+++ common/diff.php	(working copy)
@@ -41,7 +41,7 @@
 
     // execute diff
     exec("diff -au ".$name[0]." ".$name[1], $lines);
-
+    
     // delete temporary files
     for ($i = 0; $i < 2; ++$i) {
         if (!unlink($name[$i])) {
@@ -87,28 +87,40 @@
 }
 
 // compute longest common subsequence using dynamic programming
-// FIXME: both time and memory complexity can be reduced
 function lcs($a, $b) {
-    $N = mb_strlen($a);
-    $M = mb_strlen($b);
-    $C = array(array(2), array($M+1));
+    $descriptorspec = array(
+        0 => array("pipe", "r"),
+        1 => array("pipe", "w"),
+        2 => array("pipe", "w"),
+    );
 
-    for ($i = 0; $i < 2; ++$i)
-        for ($j = 0; $j <= $M; ++$j)
-            $C[$i][$j] = "";
-    
-    for ($i = 1; $i <= $N; ++$i) {
-        for ($j = 1; $j <= $M; ++$j) {
-            if (mb_substr($a, $i-1, 1) == mb_substr($b, $j-1, 1)) {
-                $C[$i%2][$j] = $C[($i-1)%2][$j-1].mb_substr($a, $i-1, 1);
-            } else if (mb_strlen($C[($i-1)%2][$j]) > mb_strlen($C[$i%2][$j-1])) {
-                $C[$i%2][$j] = $C[($i-1)%2][$j];
-            } else {
-                $C[$i%2][$j] = $C[$i%2][$j-1];
-            }
-        }
+    // run lcs process
+    $process = proc_open("iconv -f utf8 -t utf32 | " . IA_ROOT_DIR."/common/lcs" . " | iconv -f utf32 -t utf8", $descriptorspec, $pipes);
+    log_assert(is_resource($process), "Could not create process.");
+
+    // feed script to pipe
+    list($lcs_in, $lcs_out, $lcs_err) = $pipes;
+
+    fwrite($lcs_in, $a."\n");
+    fwrite($lcs_in, $b."\n");
+    fclose($lcs_in);
+
+    $result = fread($lcs_out, 10000);
+    fclose($lcs_out);
+
+    // check for errors
+    $errors = fread($lcs_err, 1000);
+    if ($errors) {
+        log_error($errors);
     }
-    return $C[$N%2][$M];
+    fclose($lcs_err);
+
+    // clean-up
+    proc_close($process);
+
+    $result = trim($result, "\n");
+
+    return $result;
 }
 
 function split_string($string, $substring, $op_name) {
Index: common/lcs.cpp
===================================================================
--- common/lcs.cpp	(revision 0)
+++ common/lcs.cpp	(revision 0)
@@ -0,0 +1,133 @@
+/*
+Longest common subsequence
+Time complexity : O(N * M)
+Memory complexity : O(N + M)
+Check for details: http://www.ics.uci.edu/~eppstein/161/960229.html
+To compile use: g++ -O2 -o lcs -static
+
+The input strings are given in UTF-32 format for convenient reading
+The output is also in UTF-32 to maintain the same format
+*/
+
+#include <cstring>
+#include <iostream>
+#include <string>
+#include <cstdio>
+#include <fstream>
+#include <vector>
+using namespace std;
+
+const int UNICODE_MARKER = 0x00FEFF;
+
+int N, M;
+
+vector <int> A, B, LCS;
+
+// keeps the last 2 lines for the length of the lcs
+int *len_prev;
+int *len_cur;
+// keeps the predecessors for the lcs
+pair<int, int> *pred_prev;
+pair<int, int> *pred_cur;
+
+void lcs(int leftA, int rightA, int leftB, int rightB)
+{
+    if (leftA > rightA) return;
+    if (leftB > rightB) return;
+
+    int i, j, middle = (leftA + rightA) >> 1; // get the middle
+
+    // initialize
+    for (i = leftB - 1; i <= rightB; i++) len_prev[i] = 0, len_cur[i] = 0, pred_prev[i] = make_pair(leftA - 1, i);
+
+    for (i = leftA; i <= rightA; i++) {
+        pred_cur[leftB - 1] = make_pair(i, leftB - 1); // another intialization
+
+        // DP
+        for (j = leftB; j <= rightB; j++) {
+            if (len_prev[j] > len_cur[j - 1]) {
+                len_cur[j] = len_prev[j];
+                pred_cur[j] = i - 1 <= middle ? make_pair(i - 1, j) : 
+                    pred_prev[j]; // update predecessor (above middle)
+            } else {
+                len_cur[j] = len_cur[j - 1];
+                pred_cur[j] = i <= middle ? make_pair(i, j - 1) : 
+                    pred_cur[j - 1]; // update predecessor (above middle)
+            }
+
+            if (A[i - 1] == B[j - 1]) {
+                len_cur[j] = len_prev[j - 1] + 1;
+                pred_cur[j] = i - 1 <= middle ? make_pair(i - 1, j - 1) : 
+                    pred_prev[j - 1]; // update predecessor (above middle)
+            }
+        }
+
+        // copy current line in previous line
+        for (j = leftB - 1; j <= rightB; j++) {
+            len_prev[j] = len_cur[j];
+               pred_prev[j] = pred_cur[j];
+        }
+    }
+
+    // if no lcs get out
+    if (len_cur[rightB] == 0) {
+        return;
+    }
+
+    if (leftA == rightA) { // check if only one line then insert solution
+        LCS.push_back(A[leftA - 1]);
+    } else if (leftB == rightB) { // check if only one column the insert solution
+        LCS.push_back(B[leftB - 1]);
+    } else { // solve for the two different parts (divide et impera)
+        pair<int, int> p = pred_cur[rightB];
+
+        lcs(leftA, p.first, leftB, p.second);
+        lcs(p.first + 1, rightA, p.second + 1, rightB);
+    }
+}
+
+int main()
+{
+    // read input strings
+
+    int chr;
+
+    // read the unicode marker
+    fread(&chr, 4, 1, stdin);
+
+    // check for UTF-32
+    if (chr != UNICODE_MARKER) {
+        return -1;
+    }
+
+    // read in UTF-32 (binary, 4 by 4 bytes)
+    do {
+        fread(&chr, 4, 1, stdin);
+        A.push_back(chr);
+    } while (chr != '\n');
+
+    do {
+        fread(&chr, 4, 1, stdin);
+        B.push_back(chr);
+    } while (chr != '\n');
+
+    N = A.size(), M = B.size();
+
+    // allocate memory
+    len_prev = new int[M + 3];
+    len_cur = new int[M + 3];
+    pred_prev = new pair<int, int>[M + 3];
+    pred_cur = new pair<int, int>[M + 3];
+
+    // run lcs
+    lcs(1, N, 1, M);
+
+    // output lcs
+    fwrite(&UNICODE_MARKER, 4, 1, stdout);
+    for (int i = 0; i < (int) LCS.size(); i++) {
+        fwrite(&LCS[i], 4, 1, stdout);
+    }
+
+    return 0;
+}
+
