最长公共子串

题目：对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。   输入"1AB2345CD",9,"12345EF",7  返回：4

思路：这道题最好想的方法就是两层for循环，如果a[i]==b[j]，维护两个指针向后指，直到他们对应的值不相等，然后比较得出max即可

但是把这道题看做最长公共子序列的类型题，实际上是简化版的LCS,只需要求dp矩阵中的一部分即可。

 public int findLongest(String A, int n, String B, int m) {
       int[][] dp=new int[n][m];
        char[] a=A.toCharArray();
        char[] b=B.toCharArray();
        int max=0;
        for(int i=0;i<n;i++){
            if(a[i]==b[0])
                dp[i][0]=1;
        }
        for(int i=0;i<m;i++){
            if(b[i]==a[0])
                dp[0][i]=1;
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(a[i]==b[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    max=Math.max(max,dp[i][j]);
                }
            }
        }
        return max;
    }