Узнайте, сколько процентов одна строка содержит в другой

Question

Мне нужно выяснить, сколько процентов или символов содержит одна строка в другой строке.Я пробовал Levenshtein Distance, но этот алгоритм возвращает, сколько символов необходимо изменить, чтобы строки были равны.Может кто-нибудь помочь?Мне это нужно в c #, но это не так важно.

Код ответа: public double LongestCommonSubsequence (строка s1, строка s2) {// если любая строка пуста, длина должна быть 0 if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty (s2)) return 0;

    int[,] num = new int[s1.Length, s2.Length];  //2D array
    char letter1;
    char letter2;

    //Actual algorithm
    for (int i = 0; i < s1.Length; i++)
    {
        letter1 = s1[i];
        for (int j = 0; j < s2.Length; j++)
        {
            letter2 = s2[j];

            if (letter1 == letter2)
            {
                if ((i == 0) || (j == 0))
                    num[i, j] = 1;
                else
                    num[i, j] = 1 + num[i - 1, j - 1];
            }
            else
            {
                if ((i == 0) && (j == 0))
                    num[i, j] = 0;
                else if ((i == 0) && !(j == 0))   //First ith element
                    num[i, j] = Math.Max(0, num[i, j - 1]);
                else if (!(i == 0) && (j == 0))   //First jth element
                    num[i, j] = Math.Max(num[i - 1, j], 0);
                else // if (!(i == 0) && !(j == 0))
                    num[i, j] = Math.Max(num[i - 1, j], num[i, j - 1]);
            }
        }//end j
    }//end i
    return (s2.Length - (double)num[s1.Length - 1, s2.Length - 1]) / s1.Length * 100; 
} //end LongestCommonSubsequence

Answer 1

Звучит так, что вам может понадобиться самая длинная общая подпоследовательность , которая является основой для алгоритмов сравнения. К сожалению, эта проблема NP-трудна, что означает, что не существует эффективного (полиномиального времени) решения. На странице Википедии есть несколько предложений.

Answer 2

Э-э-э ... не могли бы вы просто использовать количество символов, которое необходимо изменить?

(length(destination)-changed_character_count)/ length(source)

РЕДАКТИРОВАТЬ: на основе пересмотренного вопроса обрабатывать обе строки как наборы, вычислять пересечение наборови на основе процента от размера этого набора и исходной строки в виде набора.