Поиск похожих строк (LCS + Расстояние Левенштейна) (#11502)

Условие задачи

Дан набор строк $S_{1}, S_{2}, \dots, S_{n}$ (в общем случае разной длины), состоящих из строчных букв латинского алфавита.

Дана строка $T$ (запрос пользователя), также состоящая из строчных букв латинского алфавита.

Каждая строка $S_{i} (i = 1, \dots, n)$ содержит не более $k$ слов.

Строка $T$ также содержит не более $k$ слов.

Слова отделены пробелами.

Необходимо найти «наиболее похожую» на запрос пользователя строку из набора $S_{1}, S_{2}, \dots, S_{n}$ .

Будем учитывать, что:

Пользователь мог поменять слова местами.
Пользователь мог ввести только часть (подпоследовательность) строки, которую хотел найти в наборе.
Пользователь мог допустить опечатки: пропуск букв, написание лишних букв, замена букв на другие.

Решение

Рассмотрим простейшее решение.

Переберём все перестановки слов запроса $T$ .

Для каждой перестановки слов $T_{p er m u t a t i o n}$ переберем все строки $S_{i}$ , и запустим алгоритм $L CS (T_{p er m u t a t i o n}, S_{i})$ .

LCS — longest common subsequence.

Из всех строк $S_{1}, S_{2}, \dots, S_{n}$ выберем те строки, для которых величина $∣ L CS (T_{p er m u t a t i o n}, S_{i}) ∣$ — максимальна. Также запомним для какой именно перестановки $T_{p er m u t a t i o n (s a v e d)}$ была получена эта максимальная величина LCS. Обозначим полученное множество строк как $L$ .

Теперь вычислим расстояние Левенштейна между соответствующими $L_{i}$ и $T_{p er m u t a t i o n (s a v e d)}$ .

Выберем единственную строку $L_{an s}$ , для которой расстояние Левенштейна с соответствующей $T_{p er m u t a t i o n (s a v e d)}$ — минимально. Эта строка и будет ответом.

Код на 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;
}