查找一个字符串在另一个字符串中所占的百分比

Question

我需要找出一个字符串包含另一个字符串的百分比或字符数。 我尝试过Levenshtein Distance算法，但该算法返回的是使字符串相等所需更改的字符数。 有人可以帮忙吗？ 我需要使用C#编写，但这并不重要。

答案代码： public double LongestCommonSubsequence(string s1, string 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

- Pece

---

字符的顺序重要吗？ - Mark Byers

你缺少示例。这个问题非常模糊。 - Anurag

抱歉我没有写例子，好的，这里有：例1： string a = John Malkovich; string b = Joahn Mulkovich; 这两个字符串之间的差异是2个字符或者相同程度为84.6%。例2： string a = John Malkovich; string b = Jonh Malkovich; 它们的相同程度为84.6%。希望这能帮到你。 - Pece

“hcivoklaM nhoJ”是“John Malkovich”的反转，这两者相似度是0%还是84.6%呢？ - Anurag

Answer 1

听起来你可能想要最长公共子序列，这是差异算法的基础。不幸的是，这个问题是NP难问题，这意味着没有有效（多项式时间）的解决方案。维基百科页面有一些建议。

- Mark Byers

---

这里的问题只涉及2个字符串，因此可以在二次时间内完成。 - Chao Xu

现在我正在测试这个，所以我会在几分钟内写下结果。 - Pece

是的，测试顺利通过了，谢谢。 我会用C#算法编辑问题。 - Pece

Answer 2

嗯...你不能只使用需要更改的字符数量吗？

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

编辑：根据修改后的问题，将两个字符串视为集合，计算集合交集，并以该集合的大小和源字符串作为集合为基础计算百分比。

- MSN

---

我需要知道一个字符串包含另一个字符串的比例，例如在"This is Ivan Jovanov"中，“Ivan”被包含了100%。 - Pece

@Pece：这就是为什么你要比较目标字符串长度减去编辑大小与源字符串长度的Levenshtein距离。在您的测试用例中，它应该最终达到100％，因为您实际上没有从源字符串中删除任何字符。 - MSN

问题在于，如果我将“Ivan”与“Ivaxxxn”进行比较，使用“(目标长度-更改字符数)/源长度”会返回100%。 - Pece

那是一个你可能需要指定的额外约束。 - MSN