longestCommonString.java

import java.util.HashMap;

public class LongestCommonSubString {

    public static void main(String[] args) {
        long start =System.currentTimeMillis();
        String B = "abcdefg";
        String A = "xcdey";
        HashMap<String, Integer> map = new HashMap<>();
        find(A, B, map);
        System.out.println("LCS length : " + max);
        long end =System.currentTimeMillis();
        System.out.println(end-start);
    }
    static int max = 0;
    public static int find(String s1, String s2, HashMap<String, Integer> map){
        if (s1 == null || s1.length() ==0)
            return 0;

        if (s2 == null || s2.length() ==0)
            return 0;

        if(map.containsKey(s1+","+s2))
            return map.get(s1+","+s2);

        if (s1.charAt(0) == s2.charAt(0)){
            int x = find(s1.substring(1), s2.substring(1), map);
            map.put(s1.substring(1)+","+s2.substring(1), x);
            max = Math.max(1+x, max);
            return 1 + x;
        }else{
            int x = find(s1, s2.substring(1), map);
            int y = find(s1.substring(1), s2, map);
            map.put(s1+","+s2.substring(1), x);
            map.put(s1.substring(1)+","+ s2, y);
            return 0;
        }
    }
}