LCS (Longest Common Subsequence) JAVA 实现，与大家分享,希望在实现细节上，如可读性，所占空间与运行时间上面，能有更好建议

import java.util.ArrayList;

/**
* @author marshal dong
*
*/
public class LongestCommonSubString
{

/**
* @param args
*/
public static void main(String[] args)
{
             String str1 = "abcdefg";
             String str2 = "bcdeabcdgfgadefg";
              LongestCommonSubString instance = new LongestCommonSubString(str1, str2);
              instance.printLongestCommonString();
}

private String str1, str2;

public LongestCommonSubString(String str1, String str2)
{
          this.str1 = str1;
            this.str2 = str2;
}

private int[][] matrix = null;

// the list to store their respective index of multiple common sequence
private ArrayList<Integer> longestStringIndexs = new ArrayList<Integer>();

// the length of the longest common sequence
private int longestStringLength = 0;

/**
* Using a matrix to store the common sequence between the two strings, if
* matrix[i][j]=1, it indicates the two strings have the same sequence
* matrix[i][j]; but we are not simply marking 1 for the same part, we also
* calculate the length of the sequence by statement : matrix[i][j] =
* matrix[i - 1][j - 1] + 1; This way, we eliminate the need of finding
* those value that consecutively equals 1 in their diagonal direction
*/
private void constructMatrix()
{
         if (str1 == null || str1.equals("") || str2 == null || str2.equals(""))
               return;

         int len1 = str1.length();
         int len2 = str2.length();
          matrix = new int[len1][len2];

for (int i = 0; i < len1; i++)
{
       for (int j = 0; j < len2; j++)
      {
           if (str1.charAt(i) == str2.charAt(j))
           {
                    if (j == 0 || i == 0)// in this case, we don't need to do
                                                 // addition
                               matrix[i][j] = 1;
                     else
                               matrix[i][j] = matrix[i - 1][j - 1] + 1;

                     if (matrix[i][j] > longestStringLength)
                    {
                            longestStringLength = matrix[i][j];
                            longestStringIndexs.clear();// clear the former index
                            longestStringIndexs.add(i); 
                     }
                     else if (matrix[i][j] == longestStringLength)
                    {
                            longestStringIndexs.add(i); // add the new index if
                                                                        // there are more than one
                                                                        // common stirng
                     }
                } 
            }
       }
}

public void printLongestCommonString()
{ 
             constructMatrix();
             printMatrix();

              for (Integer i : longestStringIndexs)
             {
                        System.out.println(str1.substring(i - longestStringLength + 1, i + 1)); 
             }
}

private void printMatrix()
  {
          if (matrix == null)
                 return;
          for (int i = 0; i < matrix.length; i++)
          {
                      for (int j = 0; j < matrix[i].length; j++)
                     {
                                 System.out.print(matrix[i][j] + " ");
                     }
                      System.out.println();
           }
  }

}

运行结果如下 ：
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 3 0 0 0 0 0 0 0 0 0
0 0 3 0 0 0 0 4 0 0 0 0 1 0 0 0
0 0 0 4 0 0 0 0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 3 0
0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 4
abcd
bcde
defg