@@ -0,0 +1,1874 @@
+package com.interview.dynamic;%0A%0A/**%0A * http://en.wikipedia.org/wiki/Longest_common_substring_problem%0A */%0Apublic class LongestCommonSubstring %7B%0A%0A    /**%0A     * Dynamic way of calculating lcs%0A     */%0A    public int longestCommonSubstring(char str1%5B%5D, char str2%5B%5D)%7B%0A        int T%5B%5D%5B%5D = new int%5Bstr1.length+1%5D%5Bstr2.length+1%5D;%0A        %0A        int max = 0;%0A        for(int i=1; i %3C= str1.length; i++)%7B%0A            for(int j=1; j %3C= str2.length; j++)%7B%0A                if(str1%5Bi-1%5D == str2%5Bj-1%5D)%7B%0A                    T%5Bi%5D%5Bj%5D = T%5Bi-1%5D%5Bj-1%5D +1;%0A                    if(max %3C T%5Bi%5D%5Bj%5D)%7B%0A                        max = T%5Bi%5D%5Bj%5D;%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        return max;%0A    %7D%0A    %0A    /**%0A     * Recursive way of calculating lcs%0A     */%0A    public int longestCommonSubstringRec(char str1%5B%5D, char str2%5B%5D, int pos1, int pos2, boolean checkEqual)%7B%0A        if(pos1 == -1 %7C%7C pos2 == -1)%7B%0A            return 0;%0A        %7D%0A        if(checkEqual)%7B%0A            if(str1%5Bpos1%5D == str2%5Bpos2%5D)%7B%0A                return 1 + longestCommonSubstringRec(str1, str2, pos1-1, pos2-1, true);%0A            %7Delse%7B%0A                return 0;%0A            %7D%0A        %7D%0A        int r1 = 0;%0A        if(str1%5Bpos1%5D == str2%5Bpos2%5D)%7B%0A            r1 = 1 + longestCommonSubstringRec(str1, str2, pos1-1, pos2-1, true);%0A        %7D%0A        return Math.max(r1,Math.max(longestCommonSubstringRec(str1, str2, pos1-1, pos2, false), longestCommonSubstringRec(str1, str2, pos1, pos2-1,false)));%0A    %7D%0A    %0A    public static void main(String args%5B%5D)%7B%0A        LongestCommonSubstring lcs = new LongestCommonSubstring();%0A        char str1%5B%5D = %22abcdef%22.toCharArray();%0A        char str2%5B%5D = %22zcdemf%22.toCharArray();%0A        System.out.println(lcs.longestCommonSubstring(str1, str2));%0A        System.out.println(lcs.longestCommonSubstringRec(str1, str2,str1.length-1, str2.length-1,false));%0A    %7D%0A    %0A%7D%0A

Longest common substring using dp