нахождение максимально идентичных строк

В общем, вот медленный вариант, но вроде работающий.

Первым делом, код расстояние между двумя словами (просто Левенштейн)

public int MinDistance(string word1, string word2)
{
    var map = new int[word1.Length + 1, word2.Length + 1];

    for (var i = 1; i <= word1.Length; i++) map[i, 0] = i;
    for (var i = 1; i <= word2.Length; i++) map[0, i] = i;

    for (var i = 1; i <= word1.Length; i++)
    {
        for (var j = 1; j <= word2.Length; j++)
        {
            var side = Math.Min(map[i - 1, j] + 1, map[i, j - 1] + 1);
            map[i, j] = Math.Min(map[i - 1, j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 1), side);
        }
    }

    return map[word1.Length, word2.Length];
}

Зная левенштейн, можно для строк, состоящих из слов, составить матрицу сопоставления слов. Я делаю матрицу квадратной специально, чтобы потом проще было считать, ведь для расстояния между наборами слов все слова должны участвовать

public int DiffLine(string w1, string w2)
{
    var words1 = w1.Split();
    var words2 = w2.Split();
    
    var size = Math.Max(words1.Length, words2.Length);
    
    var map = new int[size, size];
    for(int i=0; i<size; i++)
        for (int j = 0; j < size; j++)
        {
            var word1 = i >= words1.Length ? string.Empty : words1[i];
            var word2 = j >= words2.Length ? string.Empty : words2[j];          
            map[i, j] = MinDistance(word1, word2);       
        }       
    
    return MinDistance(words1, words2, map, new HashSet<int>());
}

Имея мапу, я делаю тупо перебор вариантов - тут можно вроде как улучшить, у меня просто пока идей нет как =)

public int MinDistance(string[] words1, string[] words2, int[,] distances, HashSet<int> rowsTaken)
{
    if (rowsTaken.Count == distances.GetLength(0)) return 0;
    
    int ret = int.MaxValue;
    
    for(int i=0; i<distances.GetLength(0); i++)
    {
        if (rowsTaken.Contains(i)) continue;
        
        rowsTaken.Add(i);
                        
        for(int j=0; j<distances.GetLength(1); j++)
        {
            int dist = distances[i, j] + MinDistance(words1, words2, distances, rowsTaken);
            ret = Math.Min(ret, dist);          
        }
        
        rowsTaken.Remove(i);
        
    }
    
    return ret;
}

Ну и в итоге, можно сравнивать строки с учетом слов, пример кода

var wordsLeft = new[] {"вкусный пряник", "радужный"};
var wordsRight = new[] {"пряник вкусный"};

for(int i=0; i<wordsLeft.Length; i++){
    for(int j=0; j<wordsRight.Length; j++)
    {
        Console.WriteLine($"{wordsLeft[i]} <-> {wordsRight[j]} : {DiffLine(wordsLeft[i], wordsRight[j])}");
    }
}

Выдаст результат

вкусный пряник <-> пряник вкусный : 0
радужный <-> пряник вкусный : 10

Код писал на сишарпе, но на джаву он легко переносится.

Предложу еще один вариант решения этой задачи, насколько он хорошо справляется с ней судить не мне, так как по вопосу не достаточно хорошо понятно какие могут быть крайние случаи, но я постарался представить ситуацию когда меня бы его работа устроила и по времени и по качеству и по простоте логики.

Основная идея: сравнивать строки циклически смещая одну из них. Иными словами, я заметил, что при определенном смещении мы получим совпадения:

вкусный пряник
пряник вкусный

вкусный пряник
        пряник вкусный — совпадает `пряник` 

                вкусный пряник — совпадает `вкусный`
         пряник вкусный

Таким образом мы как-бы ищем совпадения паттернов, хотя этот способ обладает рядом погрешностей, вот пример цикла сравнения с замером количества совпадений букв.

0 три два раз  раз два три  3  - тут `два` совпало с `два`
1 три два раз  аз два три р 1
2 три два раз  з два три ра 0
3 три два раз   два три раз 0
4 три два раз  два три раз  3  - тут `раз` совпал с `раз`
5 три два раз  ва три раз д 0
6 три два раз  а три раз дв 0
7 три два раз   три раз два 1
8 три два раз  три раз два  3  - тут `три` совпало с `три`
9 три два раз  ри раз два т 1
10 три два раз  и раз два тр 0
11 три два раз   раз два три 1

Весь код решения в качестве ответа диапазон от 0 до 1 (1 совпадение):

import java.util.*;

public class Main {

    // Cравниваем посимвольно две строки (идя по самой короткой)
    // а так же учитываем максимальную длину таких совпадений
    // чтобы откинуть варианты где буквы будут просто перемешаны
    public static int[] compare(String a, String b, int[] mem) {
        int till = Math.min(a.length(), b.length()); // меньший цикл
        int max_len = 0;       // максимальная длина совпадения
        int pattern_size = 0;  // длина совпадения
        int[] ret = new int[a.length()]; 
        for (int i = 0; i < till; i++) {
            if (a.charAt(i) == b.charAt(i) && a.charAt(i) != ' ') {
                ret[i] = 1 + mem[i]; // накапливаем
                pattern_size += 1;
            } else if (a.charAt(i) != b.charAt(i) && a.charAt(i) != ' ') {
                ret[i] = mem[i]; // переносим предыдущий опыт
            } else {
                if (max_len < pattern_size) {
                    max_len = pattern_size;
                }
                pattern_size = 0;
            }
        }
        if (max_len < 3) return mem;
        return ret;
    }

    // Функция считает количество не нулевых элементов массива
    // Нулевыми в данном случае будут либо `пробелы`,
    // либо не совпадающие буквы.
    public static int calc(int[] mem) {
        int sum = 0;
        for (int i : mem) if (i != 0) sum += 1;
        return sum;
    }

    // Функция сравнивает 2 строки `a` и `b` 
    // строка `b` циклически прокручивается
    // чтобы найти максимальные совпадения со строкой `a`
    public static double test(String a, String b) {
        int[] mem = new int[a.length()]; // тут накапливаем сравнения 
        a += ' ';
        b += ' ';
        for (int i = 0; i < b.length(); i++) {
          String n = b.substring(i) + b.substring(0, i);
          //System.out.println(n);
          mem = compare(a, n, mem);
        }
        double letters = (double)a.replace(" ", "").length();
        double result = calc(mem) / letters;
        return result;
    }

    public static void main(String[] args) {
        System.out.println(test("пряник вкусный", "вкусный пряник")); // 1.0
        System.out.println(test("пряник вкусный", "впкруяс нныийк")); // 0.0 (пример шума)
        System.out.println(test("раз два три", "три два раз")); // 1.0
        System.out.println(test("раз два три", "три три три")); // 0.33 ("раз" и "два" нет)
        System.out.println(test("три три три", "раз два три")); // 1.0 (три в 3х позициях) 
        System.out.println(test("вкусный пряник", "радужный")); // 0.30 ("у" и "ный" )
        System.out.println(test("пряник вкусный", "пряник вкусны")); // 0.92  
        System.out.println(test("пряник вкусный", "пряник вкуснй")); // 0.84  
        System.out.println(test("пряник вкусный", "пряник вкуснйы")); // 0.84  

    }
}

Значения pattern_size и max_len в функции compare позволяют не считать слова с перемешанными буквами одинаковыми, (max_len < 3) таким образом отбрасывает шум при сравнении строк (вторая строка в тесте выдаст ноль). До этого я реализовывал алгоритм без учета этих значений и он был не более полезным, чем сравнение наличия букв в обоих фразах