Skip to content

Instantly share code, notes, and snippets.

@hydra1983
Created November 18, 2013 06:27
Show Gist options
  • Save hydra1983/7523506 to your computer and use it in GitHub Desktop.
Save hydra1983/7523506 to your computer and use it in GitHub Desktop.
Longest Common Substring
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment