找出一個字符串在另一個字符串中包含多少百分比

我需要找出一個字符串包含在另一個字符串中的百分比或字符數。我試過了Levenshtein距離，但是那個算法返回需要多少字符來改變字符串是否相等。有人可以幫忙嗎？我需要它在C＃但這並不重要。找出一個字符串在另一個字符串中包含多少百分比

答案代碼：公共雙LongestCommonSubsequence（串S1，字符串s2） { //如果任一字符串是空的，長度必須爲0 如果（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

來源

2010-06-18 Pece

字符的順序是否重要？ – 2010-06-18 23:13:39

你缺少的例子。這個問題非常模糊。 – Anurag 2010-06-18 23:23:00

我不好寫的例子，確定他們是:) 例如： string a = John Malkovich; string b = Joahn Mulkovich; 這些字符串之間的差異是2個字符，或者它們是相同的84.6％。例如， 2： string a = John Malkovich; string b = Jonh Malkovich; 他們是一樣的84.6％希望我會有所幫助。 – Pece 2010-06-18 23:32:51

這聽起來像你可能想longest common subsequence這是差異算法的基礎。不幸的是，這個問題是NP-hard，這意味着沒有有效的（多項式時間）解決方案。維基百科頁面有一些建議。

來源

2010-06-18 23:19:44

這裏的問題只考慮2個字符串，因此它可以在二次時間完成。 – 2010-06-18 23:57:47

現在寫我正在測試這個，所以我會在幾分鐘內寫出結果。 – Pece 2010-06-19 00:06:55

好的，測試進行得很順利，謝謝。我將用c＃算法編輯問題。 – Pece 2010-06-19 00:23:03

呃......難道你不能只使用需要改變的字符數嗎？

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

編輯：基於所述修正的問題，同時治療的字符串作爲集，計算交集，和鹼的百分比關閉該組的大小和所述源串作爲一組。

來源

2010-06-18 23:18:16 MSN

我需要多少個字符串包含到另一個字符串中，例如「這是伊萬約萬諾夫」中的「伊凡」包含100％。 – Pece 2010-06-18 23:35:12

@Pece：Levenshtein距離會告訴你。這就是爲什麼您將目標字符串的長度減去編輯的大小與源字符串的長度進行比較的原因。在你的測試用例中，它最終應該是100％，因爲你實際上並沒有從源字符串中刪除任何字符。 – MSN 2010-06-18 23:37:50

這裏的問題是，如果我將「Ivan」與「Ivaxxxn」進行比較，如果我使用：「（length（destination）-changed_character_count）/ length（source）」，它將返回100％ – Pece 2010-06-18 23:58:05

找出一個字符串在另一個字符串中包含多少百分比

回答

相關問題