Déterminez le pourcentage que contient une chaîne dans un autre

Question

J'ai besoin de connaître le pourcentage ou le nombre de caractères contenus dans une chaîne dans une autre chaîne. J'ai essayé Levenshtein Distance mais cet algorithme retourne la quantité de caractères à changer pour que les chaînes soient égales. Quelqu'un peut-il m'aider? J'en ai besoin en C# mais ce n'est pas si important.

Le code de réponse: à double LongestCommonSubsequence publique (chaîne s1, chaîne s2) {// si l'une chaîne est vide, la longueur doit être de 0 si (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

On dirait que vous voudrez peut-être le longest common subsequence qui est la base pour les algorithmes de diff. Malheureusement, ce problème est NP-difficile, ce qui signifie qu'il n'y a pas de solution efficace (temps polynomial). La page Wikipedia a quelques suggestions.

Answer 2

Euh ... ne pouvez-vous pas simplement utiliser le nombre de caractères qui doivent changer alors?

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

EDIT: en fonction de la question révisée, traiter les deux chaînes comme des ensembles, calculer l'intersection de jeu et la base du pourcentage de la taille de cet ensemble et la chaîne source comme un ensemble.