/* P0003:
 * Find the longest common sequence between two strings.
 * */

public class P0003 {
  public static int lcs(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();

    int[][] r = new int[n + 1][m + 1];
    int[][] s = new int[n + 1][m + 1];

    int res = lcsHelper(s1, s2, r, s);
    return res;
  }

  private static int lcsHelper(String s1, String s2, int[][] r, int[][] s) {
    int res = 0;

    int n = r.length;
    int m = r[0].length;

    for (int i = 1; i < n; i++) {
      for (int j = 1; j < m; j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
          r[i][j] = r[i - 1][j - 1] + 1;

          if (r[i][j] > res)
            res = r[i][j];
        }
        else {
          r[i][j] = 0;
        }
      }
    }

    return res;
  }

  public static void main(String[] args) {
    String s1 = "satrday";
    String s2 = "sunday";

    int res = P0003.lcs(s1, s2);
    System.out.println(res);
  }
}

@@ -91,26 +91,87 @@
 03 %7B%0A  p
-ublic stat
+rivate class Result %7B%0A    int maxLen;%0A    int i;%0A    int j;%0A  %7D%0A%0A  publ
 ic int l
@@ -291,87 +291,162 @@
 1%5D;%0A
+%0A
     
-int%5B%5D%5B%5D s = new int%5Bn + 1%5D%5Bm + 1%5D;%0A%0A    int res = lcsHelper(s1, s2, r, s
+Result res = lcsHelper(s1, s2, r);%0A    for (int i = 0; i %3C res.maxLen; i++)%0A      System.out.print(s1.charAt(res.i + i));%0A    System.out.println(
 );%0A
+%0A
     
@@ -447,32 +447,39 @@
 %0A%0A    return res
+.maxLen
 ;%0A  %7D%0A%0A  private
@@ -483,17 +483,13 @@
 ate 
-static in
+Resul
 t lc
@@ -531,27 +531,16 @@
 %5B%5D r
-, int%5B%5D%5B%5D s
 ) %7B%0A    
 int 
@@ -535,26 +535,29 @@
 ) %7B%0A    
-in
+Resul
 t res = 
 0;%0A%0A    
@@ -548,17 +548,28 @@
 t res = 
-0
+new Result()
 ;%0A%0A    i
@@ -802,17 +802,26 @@
 j%5D %3E res
-)
+.maxLen) %7B
 %0A       
@@ -828,16 +828,23 @@
      res
+.maxLen
  = r%5Bi%5D%5B
@@ -847,16 +847,137 @@
 %5Bi%5D%5Bj%5D;%0A
+            // record the start of the LCS%0A            res.i = i - r%5Bi%5D%5Bj%5D;%0A            res.j = j - r%5Bi%5D%5Bj%5D;%0A          %7D%0A
         
@@ -1101,24 +1101,56 @@
 g%5B%5D args) %7B%0A
+    P0003 p0003 = new P0003();%0A%0A
     String s
@@ -1205,17 +1205,17 @@
 t res = 
-P
+p
 0003.lcs

print the lcs