Skip to content

Instantly share code, notes, and snippets.

@DonKeyHot1
Created June 17, 2018 17:35
Show Gist options
  • Save DonKeyHot1/9a4de9fddec9251d8a05cc47e3e40434 to your computer and use it in GitHub Desktop.
Save DonKeyHot1/9a4de9fddec9251d8a05cc47e3e40434 to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
String stringOne;
String stringTwo;
if (args.length > 2) {
stringOne = args[0];
stringTwo = args[1];
} else {
stringOne = "мама мыла раму";
stringTwo = "саша мыл раму";
}
List<String> longestCommonSubstrings = getLongestCommonSubstrings(stringOne, stringTwo);
StringBuilder result = new StringBuilder();
if (longestCommonSubstrings == null || longestCommonSubstrings.size() == 0) {
result.append("Общих подстрок не найдено.");
} else if (longestCommonSubstrings.size() == 1) {
result.append("Найдена одна наибольшая общая подстрока: ");
} else {
int size = longestCommonSubstrings.size();
result.append("Всего найдено ")
.append(size)
.append(" различных подстрок наибольшей длины длины: ");
}
if (longestCommonSubstrings != null) {
for (String lcs : longestCommonSubstrings) {
result.append('\n');
result.append(lcs);
}
}
System.out.println(result.toString());
}
private static List<String> getLongestCommonSubstrings(String stringOne, String stringTwo) {
int stringOneLength = stringOne.length();
int stringTwoLength = stringTwo.length();
int matchTable[][] = new int[stringOneLength][stringTwoLength];
List<String> result = null;
int maxLength = Integer.MIN_VALUE;
for (int i = 0; i < stringOneLength; i++) {
for (int j = 0; j < stringTwoLength; j++) {
if (stringOne.charAt(i) == stringTwo.charAt(j)) {
if (i == 0 || j == 0) matchTable[i][j] = 1;
else matchTable[i][j] = matchTable[i - 1][j - 1] + 1;
if (matchTable[i][j] > maxLength) {
maxLength = matchTable[i][j];
result = new ArrayList<>();
result.add(stringOne.substring(i - maxLength + 1, i + 1));
} else if (matchTable[i][j] == maxLength) {
result.add(stringOne.substring(i - maxLength + 1, i + 1));
}
} else {
matchTable[i][j] = 0;
}
}
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment