LCS.java

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;
    }
}