Условие задачи
Дан набор строк $$${S}_{1}, {S}_{2}, \ldots, {S}_{n}$$$ (в общем случае разной длины), состоящих из строчных букв латинского алфавита.
Дана строка $$$T$$$ (запрос пользователя), также состоящая из строчных букв латинского алфавита.
Каждая строка $$${S}_{i} (i = 1, \dots, n)$$$ содержит не более $$$k$$$ слов.
Строка $$$T$$$ также содержит не более $$$k$$$ слов.
Слова отделены пробелами.
Необходимо найти «наиболее похожую» на запрос пользователя строку из набора $$${S}_{1}, {S}_{2}, \dots, {S}_{n}$$$.
Будем учитывать, что:
Пользователь мог поменять слова местами.
Пользователь мог ввести только часть (подпоследовательность) строки, которую хотел найти в наборе.
Пользователь мог допустить опечатки: пропуск букв, написание лишних букв, замена букв на другие.
Решение
Рассмотрим простейшее решение.
Переберём все перестановки слов запроса $$$T$$$.
Для каждой перестановки слов $$${T}_{permutation}$$$ переберем все строки $$${S}_{i}$$$, и запустим алгоритм $$$LCS({T}_{permutation}, {S}_{i})$$$.
LCS — longest common subsequence.
Из всех строк $$${S}_{1}, {S}_{2}, \dots, {S}_{n}$$$ выберем те строки, для которых величина $$$|LCS({T}_{permutation}, {S}_{i})|$$$ — максимальна. Также запомним для какой именно перестановки $$${T}_{permutation(saved)}$$$ была получена эта максимальная величина LCS. Обозначим полученное множество строк как $$$L$$$.
Теперь вычислим расстояние Левенштейна между соответствующими $$${L}_{i}$$$ и $$${T}_{permutation(saved)}$$$.
Выберем единственную строку $$${L}_{ans}$$$, для которой расстояние Левенштейна с соответствующей $$${T}_{permutation(saved)}$$$ — минимально. Эта строка и будет ответом.
Код на Java:
public int F(char x, char y)
{
if (x == y) return 0;
else return 1;
}
public int GetDist(String a, String b)
{
int[][] D = new int[100][100];
D[0][0] = 0;
for (int i = 1; i < a.length(); i++)
{
D[i][0] = i;
}
for (int j = 1; j < b.length(); j++)
{
D[0][j] = j;
}
for (int i = 1; i < a.length(); i++)
{
for (int j = 1; j < b.length(); j++)
{
int m = F(a.charAt(i), b.charAt(j));
int val1 = D[i][j-1] + 1;
int val2 = D[i-1][j] + 1;
int val3 = D[i-1][j-1] + m;
int minv = Math.min(val1, val2);
minv = Math.min(minv, val3);
D[i][j] = minv;
}
}
return D[a.length()-1][b.length()-1];
}
public String[] swap(String data[], int left, int right)
{
// Swap the data
String temp = data[left];
data[left] = data[right];
data[right] = temp;
// Return the updated array
return data;
}
public int Compare(String a, String b)
{
for (int i = 0; i < Math.min(a.length(), b.length()); i++)
{
if (a.charAt(i) < b.charAt(i))
{
return -1;
}
if (a.charAt(i) > b.charAt(i))
{
return 1;
}
}
if (a.length() < b.length()) return -1;
if (a.length() > b.length()) return 1;
return 0;
}
public String[] findNextPermutation(String p[])
{
for (int a = p.length - 2; a >= 0; --a)
{
if (Compare(p[a], p[a+1]) == -1)
{
for (int b = p.length-1; ; --b)
{
if (Compare(p[b], p[a]) == 1)
{
String t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length-1; a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return p;
}
}
}
}
return p;
}
public int Factorial(int n)
{
int fact = 1;
for (int i = 2; i <= n; i++)
{
fact *= i;
}
return fact;
}
public int GetLenMaxSubSeq(String a, String b)
{
int[][] dp = new int[100][100];
dp[0][0] = 0;
for (int i = 1; i <= a.length(); i++)
{
dp[i][0] = 0;
}
for (int j = 1; j <= b.length(); j++)
{
dp[0][j] = 0;
}
for (int i = 1; i <= a.length(); i++)
{
for (int j = 1; j <= b.length(); j++)
{
if (a.charAt(i-1) == b.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]);
}
}
int maxv = 0;
for (int i = 0; i <= a.length(); i++)
{
for (int j = 0; j <= b.length(); j++)
{
if (dp[i][j] > maxv)
{
maxv = dp[i][j];
}
}
}
return maxv;
}
public Pair PermutateSubSeq(String a, String b)
{
int max_len = 0;
String[] b_arr = b.split("\\s+");
Arrays.sort(b_arr);
String res = "";
for (int cur_permutation = 0; cur_permutation < Factorial(b_arr.length); cur_permutation++)
{
int cur_len = GetLenMaxSubSeq(a, b);
if (cur_len > max_len)
{
max_len = cur_len;
res = b;
}
b_arr = findNextPermutation(b_arr);
b = "";
for (int i = 0; i < b_arr.length-1; i++)
{
b += b_arr[i] + " ";
}
b += b_arr[b_arr.length-1];
}
Pair pair = new Pair();
pair.Val = max_len;
pair.str = res;
return pair;
}
public int GetIndex(String name, int N)
{
int index = 0;
int maxlensubseq = 0;
int min_dist = 10000;
for (int i = 0; i < N; i++)
{
Pair p = PermutateSubSeq(arr[i], name);
int cur_subseq_len = p.Val;
String str = p.str;
if (cur_subseq_len > maxlensubseq)
{
maxlensubseq = cur_subseq_len;
index = i;
}
if (cur_subseq_len == maxlensubseq)
{
int cur_dist = GetDist(arr[i], str);
if (cur_dist < min_dist)
{
min_dist = cur_dist;
index = i;
}
}
}
return index;
}
