Longest Common Substring

LongestCommonSubstring.java

public class LongestCommonSubstring {
	public static void main(String[] args) {
		String str1 = "21232523311324";
		String str2 = "312123223445";
		String lcs = lcs(str1, str2);

		System.out.println(lcs);
		System.out.println(lcs.length());
	}

	private static String lcs(String input1, String input2) {
		if (input1 == null || input2 == null) {
			return "";
		}

		int len1 = input1.length();
		int len2 = input2.length();
		int[][] lenMatrix = new int[len1][len2];

		int len = 0;
		int start = 0;
		int end = 0;
		for (int row = 0; row < len1; row++) {
			for (int col = 0; col < len2; col++) {
				if (input1.charAt(row) == input2.charAt(col)) {
					if (row == 0 || col == 0) {
						lenMatrix[row][col] = 1;
					} else {
						lenMatrix[row][col] = lenMatrix[row - 1][col - 1] + 1;
					}
				} else {
					lenMatrix[row][col] = 0;
				}

				if (lenMatrix[row][col] > len) {
					len = lenMatrix[row][col];
					end = col;
				}
			}
		}

		start = end - len + 1;
		String result = "";
		for (int i = start; i <= end; i++) {
			result += input2.charAt(i);
		}
		return result;
	}
}