Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
Add Comment
Please, Sign In to add comment