Longest Common Sequence.

LCS.java

import java.util.*;
import java.math.*;

public class LCS {
    public static void main(String[] args) {
       LCS_ l = new LCS_();
       System.out.println(l.lCSR("AGGTAB", "GXTXAYB", 0, 0));
       System.out.println(l.lCSR("pmjghexybyrgzczy", "hafcdqbgncrcbihkd", 0, 0));
       System.out.println(l.lCSR("oxcpqrsvwf","shmtulqrypy", 0, 0));

       l.cc();
       String f = "pmjghexybyrgzczy";
       String s = "hafcdqbgncrcbihkd";
       System.out.println(l.lCSDP(f, s, 0, 0));
       l.cc();
       f = "oxcpqrsvwf"; s = "shmtulqrypy";
       System.out.println(l.lCSDP(f, s, 0, 0));
       l.cc();
       f = "arafat"; s = "fast";
       System.out.println(l.lCSDP(f, s, 0, 0));
       
    }
}

class LCS_ {
    /*
    public int lCSR(String text1, String text2) {
        if(text1.length() == 0 || 
           text2.length() == 0) { 
            return 0; 
        }
        if(text1.charAt(0) == 
               text2.charAt(0)) { 
            return 1 + lCSR(text1.substring(1), 
                            text2.substring(1)); 
        }
        return Math.max(lCSR(text1.substring(1), text2), 
                        lCSR(text1, text2.substring(1)));
    }
    */

    int[][] cache = new int[1000][1000];
    public void cc() {for(int[] array: cache){Arrays.fill(array, -1);}}
    public int lCSRM(String text1, String text2, int m, int n) {
        if(m == 0 || n == 0) {
            return 0;
        }
        if(cache[m - 1][n - 1] != -1) {
            return cache[m - 1][n - 1];
        }
        if(text1.charAt(m - 1) == text2.charAt(n - 1)) {
            cache[m - 1][n - 1] = 
                1 + lCSRM(text1, text2, m - 1, n - 1);
            return cache[m - 1][n - 1];
        }
        cache[m - 1][n - 1] = Math.max(lCSRM(text1, text2, m, n - 1),
                                       lCSRM(text1, text2, m - 1, n));
        return cache[m - 1][n - 1];
    }

    public int lCSDP(String text1, String text2, int m, int n) {
        if(m == text1.length() || n == text2.length()) {
            return 0;
        }
        if(cache[m][n] != -1) {
            return cache[m][n];
        }
        if(text1.charAt(m) == text2.charAt(n)) {
            cache[m][n] =
                1 + lCSDP(text1, text2, m + 1, n + 1);
            return cache[m][n];
        }
        cache[m][n] = Math.max(lCSDP(text1, text2, m, n + 1),
                               lCSDP(text1, text2, m + 1, n));
        return cache[m][n];
    }

  public int lCSR(String text1,
                  String text2,
                  int m,
                  int n) {
    if(m == text1.length() ||
       n == text2.length()) {
       return 0;
    }
    if(text1.charAt(m) ==
       text2.charAt(n)) {
      return 1 + lCSR(text1, text2,
                      m + 1, n + 1);
    }
    return Math.max(lCSR(text1, text2, m, n + 1),
                    lCSR(text1, text2, m + 1, n));
     
  }
}