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
?
