LCS：最长公共子序列。
例：A{a,d,h,e,g,s,l} B{y,a,r,e,s,d}
LCS< A,B >={a,e,s}

思路：设A{a1,a2,…,an} B{b1,b2,…,bm}
若an==bm;则LCS< A,B >=LCS< A(n-1),B(m-1) >+an/bm
若an!=bm;则LCS< A,B >=LCS< A(n-1),B >或LCS< A,B >=LCS< A,B(m-1) >,即LCS< A,B >=max{LCS< A(n-1),B >，LCS< A,B(m-1) >}

Java实现

public class LCS {  
    private final static String[] empty = new String[0];  

    /** * @return 最长公共字符串(可能有多个长度相同的) */  
    public static String[] lcs(String s1, String s2, boolean noRepeat) {  
        //排除常用情况 
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {  
            return empty;  
        }  
        int len1 = s1.length();  
        int len2 = s2.length();  
        if (len1==len2&&s1.equals(s2)) {  
            return new String[] { s1 };  
        }  
        if (len1 > len2 && s1.indexOf(s2) != -1) {  
            return new String[] { s2 };  
        }  
        if (len2 > len1 && s2.indexOf(s1) != -1) {  
            return new String[] { s1 };  
        }  
        //构造对比矩阵 
        char[] chs1 = s1.toCharArray();  
        char[] chs2 = s2.toCharArray();  
        boolean[][] as = new boolean[len1][len2];  
        for (int i = 0; i < len1; i++) {  
            char ch1 = chs1[i];  
            for (int j = 0; j < len2; j++) {  
                char ch2 = chs2[j];  
                as[i][j] = ch1 == ch2;  
            }  
        }  
        // 收集正向\对角线 
        int max = 0;  
        Collection<String> buf = noRepeat ? (new HashSet<String>())  
                : (new ArrayList<String>());  
        for (int i = 0; i < len1; i++) {  
            for (int j = 0; j < len2; j++) {  
                int len = lcsLength(i, j, len1, len2, as);  
                if (len > 0 && len >= max) {  
                    max = len;  
                    buf.add(s1.substring(i, i + len));  
                }  
            }  
        }  
        // 取最长对角线(最长匹配字符) 
        List<String> ret = new ArrayList<String>();  
        for (String s : buf) {  
            if (s.length() == max) {  
                ret.add(s);  
            }  
        }  
        return ret.toArray(empty);  
    }  

    /** * 递归计算长度(对角线) */  
    private static int lcsLength(int i, int j, int len1, int len2,  
            boolean[][] as) {  
        if (as[i][j]) {  
            int c = 1;  
            i++;  
            j++;  
            if (i < len1 && j < len2) {  
                c += lcsLength(i, j, len1, len2, as);  
            }  
            return c;  
        }  
        return 0;  
    }  

    public static void main(String[] args) {  
        {  
            String s1 = "12345";  
            String s2 = "12456";  
            // 输出[45,12] 
            System.out.println(Arrays.asList(lcs(s1, s2, true)));  
        }  
        {  
            String s1 = "123456";  
            String s2 = "1205678";  
            // 输出[56,12] 
            System.out.println(Arrays.asList(lcs(s1, s2, true)));  
        }  
    }  
}