Plus longue sous-séquence commune pour une série de chaînes

Question

Pour le Longest Common Subsequence de 2 chaînes j'ai trouvé beaucoup d'exemples en ligne et je crois que je comprends la solution.
Ce que je ne comprends pas est, quelle est la bonne façon d'appliquer ce problème pour N Strings? La même solution est-elle appliquée d'une manière ou d'une autre? Comment? La solution est-elle différente? Quelle?

Answer 1

Ce problème devient NP-hard lorsque l'entrée a un nombre arbitraire de chaînes. Ce problème devient traitable seulement lorsque l'entrée a un nombre fixe de chaînes. Si l'entrée a k chaînes, nous pourrions appliquer la même technique DP en utilisant un tableau de dimension k pour trouver des solutions optimales de sous-problèmes.

Référence: Longest common subsequence problem

Answer 2

Pour trouver le Subsequence Longest Common (LCS) de 2 chaînes A et B, vous pouvez traverser un tableau à 2 dimensions en diagonale comme indiqué dans le Link que vous avez publié. Chaque élément du tableau correspond au problème de trouver le LCS des sous-chaînes A 'et B' (A coupé par son numéro de rangée, B coupé par son numéro de colonne). Ce problème peut être résolu en calculant la valeur de tous les éléments du tableau. Vous devez être certain que lorsque vous calculez la valeur d'un élément de tableau, tous les sous-problèmes requis pour calculer cette valeur donnée ont déjà été résolus. C'est pourquoi vous traversez le tableau à deux dimensions en diagonale. Cette solution peut être mise à l'échelle pour trouver la plus longue sous-séquence commune entre N chaînes, mais cela nécessite une manière générale d'itérer un tableau de N dimensions de sorte que tout élément est atteint seulement lorsque tous les sous-problèmes de l'élément nécessitent une solution. a été résolu. Au lieu d'itérer le tableau N-dimensional dans un ordre spécial, vous pouvez également résoudre le problème de manière récursive. Avec la récursivité, il est important de sauvegarder les solutions intermédiaires, car de nombreuses branches nécessiteront les mêmes solutions intermédiaires. Je l'ai écrit un petit exemple C# qui fait cela:

string lcs(string[] strings) 
{ 
    if (strings.Length == 0) 
     return ""; 
    if (strings.Length == 1) 
     return strings[0]; 
    int max = -1; 
    int cacheSize = 1; 
    for (int i = 0; i < strings.Length; i++) 
    { 
     cacheSize *= strings[i].Length; 
     if (strings[i].Length > max) 
      max = strings[i].Length; 
    } 
    string[] cache = new string[cacheSize]; 
    int[] indexes = new int[strings.Length]; 
    for (int i = 0; i < indexes.Length; i++) 
     indexes[i] = strings[i].Length - 1; 
    return lcsBack(strings, indexes, cache); 
} 
string lcsBack(string[] strings, int[] indexes, string[] cache) 
{ 
    for (int i = 0; i < indexes.Length; i++) 
     if (indexes[i] == -1) 
      return ""; 
    bool match = true; 
    for (int i = 1; i < indexes.Length; i++) 
    { 
     if (strings[0][indexes[0]] != strings[i][indexes[i]]) 
     { 
      match = false; 
      break; 
     } 
    } 
    if (match) 
    { 
     int[] newIndexes = new int[indexes.Length]; 
     for (int i = 0; i < indexes.Length; i++) 
      newIndexes[i] = indexes[i] - 1; 
     string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]]; 
     cache[calcCachePos(indexes, strings)] = result; 
     return result; 
    } 
    else 
    { 
     string[] subStrings = new string[strings.Length]; 
     for (int i = 0; i < strings.Length; i++) 
     { 
      if (indexes[i] <= 0) 
       subStrings[i] = ""; 
      else 
      { 
       int[] newIndexes = new int[indexes.Length]; 
       for (int j = 0; j < indexes.Length; j++) 
        newIndexes[j] = indexes[j]; 
       newIndexes[i]--; 
       int cachePos = calcCachePos(newIndexes, strings); 
       if (cache[cachePos] == null) 
        subStrings[i] = lcsBack(strings, newIndexes, cache); 
       else 
        subStrings[i] = cache[cachePos]; 
      } 
     } 
     string longestString = ""; 
     int longestLength = 0; 
     for (int i = 0; i < subStrings.Length; i++) 
     { 
      if (subStrings[i].Length > longestLength) 
      { 
       longestString = subStrings[i]; 
       longestLength = longestString.Length; 
      } 
     } 
     cache[calcCachePos(indexes, strings)] = longestString; 
     return longestString; 
    } 
} 
int calcCachePos(int[] indexes, string[] strings) 
{ 
    int factor = 1; 
    int pos = 0; 
    for (int i = 0; i < indexes.Length; i++) 
    { 
     pos += indexes[i] * factor; 
     factor *= strings[i].Length; 
    } 
    return pos; 
} 

Mon exemple de code peut être encore optimisé. La plupart des chaînes mises en cache sont des doublons et certaines sont des doublons avec un seul caractère supplémentaire ajouté. Cela utilise plus d'espace que nécessaire lorsque les chaînes d'entrée deviennent volumineuses.

En entrée: "666222054263314443712", "5432127413542377777", "6664664565464057425"

Le LCS est retourné "54442"