src/main/java/edu/mai/pastsolution/LcsSimilarity.java - master - monzikov/past-solution

src/main/java/edu/mai/pastsolution/LcsSimilarity.java
130 строк6 KB
Yuri Monzikov
add past-solution code
04 июл 2026, 14:38
04 июл 2026, 14:381516693
package edu.mai.pastsolution;

import java.util.*;
import java.util.stream.Collectors;

public class LcsSimilarity {

    /**
     * Возвращает все возможные комбинации подстрок (непустых) для заданной строки.
     * Например, для "ABC" вернет ["A", "B", "C", "AB", "BC", "ABC"] только отсортированный по длине.
     */
    public List<String> getAllSubstrings(String str) {
        List<String> subsequences = new ArrayList<>();
        if (str == null || str.isEmpty()) {
            return new ArrayList<>();
        }
        str = str.toUpperCase();
        int n = str.length();

        // Всего комбинаций: (2^n) - 1. Перебираем маски от 1 до (2^n - 1)
        // Маска определяет, какие индексы символов мы берем (если бит установлен в 1)
        int totalCombinations = 1 << n; // 2^n

        for (int mask = 1; mask < totalCombinations; mask++) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < n; i++) {
                // Проверяем, установлен ли i-й бит в текущей маске
                if ((mask & (1 << i)) != 0) {
                    sb.append(str.charAt(i));
                }
            }
            subsequences.add(sb.toString().toUpperCase());
        }

        // Удаляем дубликаты (актуально, если в строке есть одинаковые буквы)
        // и сортируем по длине на убывание
        return subsequences.stream()
                .distinct()
                .sorted(Comparator.comparingInt(String::length).reversed())
                .collect(Collectors.toList());
    }

    /**
     * Возвращает отобранные магическим подбором комбинации подстрок LCS (непустых) для заданной строки.
     * Например, для "ИВАНОВ" вернет все подстроки вплоть до "ИВАН"
     */
    public List<String> getLcsSubstrings(String str) {
        List<String> subsequences = new ArrayList<>();
        if (str == null || str.isEmpty()) {
            return new ArrayList<>();
        }
        str = str.toUpperCase();
        int n = str.length();

        int totalCombinations = 1 << n; // 2^n
        for (int mask = 1; mask < totalCombinations; mask++) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < n; i++) {
                // Проверяем, установлен ли i-й бит в текущей маске
                if ((mask & (1 << i)) != 0) {
                    sb.append(str.charAt(i));
                }
            }
            var lcs_sim = calculateSimilarity(sb.toString().toUpperCase(), str);
            double LcsMagicNum = 0.8915;
            var sim_max = 2-(LcsMagicNum +Math.log(n+1))/Math.log(n+1);
            if (lcs_sim >= sim_max)
                subsequences.add(sb.toString());
        }

        // Удаляем дубликаты (актуально, если в строке есть одинаковые буквы)
        // и сортируем по длине на убывание
        return subsequences.stream()
                .distinct()
                .sorted(Comparator.comparingInt(String::length).reversed())
                .collect(Collectors.toList());
    }

    /**
     * Вычисляет сходство двух строк на основе алгоритма LCS (Наибольшая общая подпоследовательность).
     * Результат нормируется по максимальной длине одной из двух строк: LCS_Length / max(str1.length, str2.length).
     * Возвращает значение от 0.0 (полное различие) до 1.0 (полное совпадение).
     */
    public double calculateSimilarity(String str1, String str2) {
        if (str1 == null || str2 == null) {
            return 0.0;
        }
        if (str1.isEmpty() && str2.isEmpty()) {
            return 1.0;
        }

        int maxLength = Math.max(str1.length(), str2.length());

        int lcsLength = getLcsLength(str1, str2);

        // Метрика сходства: отношение длины LCS к максимальной длине одной из строк
        return (double) lcsLength / maxLength;
    }

    public double calculateSimilarityWithIcanTransliterator(String str1, String str2) {
        var res_1 = IcanTransliterator.transliterate(str1);
        var res_2 = IcanTransliterator.transliterate(str2);
        return Math.max(calculateSimilarity(res_1, res_2), calculateSimilarity(str1, str2));
    }

    /**
     * Вспомогательный метод для поиска длины LCS с помощью динамического программирования.
     */
    private int getLcsLength(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        // Матрица для хранения длин подпоследовательностей
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

}