Comment obtenir des indices de sous-séquences de chaînes après avoir compté le nombre de sous-séquences?

Question

Étant donné l'algorithme suivant pour compter le nombre de fois qu'une chaîne de caractères apparaît en tant que sous-séquence d'une autre et me donner le nombre final, comment pourrais-je implémenter une routine pour me donner les indices des chaînes. Par exemple, s'il y a 4 chaînes apparaissant comme une sous-séquence d'une autre, comment pourrais-je trouver les indices de chaque chaîne? De ma propre tentative pour résoudre le problème, il y a un modèle sur la table de recherche dp que je vois visuellement, mais que j'ai du mal à implémenter dans le code, comment ajouter un retour arrière qui serait donnez-moi les indices de chaque sous-séquence de chaîne telle qu'elle apparaît. Dans l'exemple, je connais le nombre de fois que la chaîne apparaîtra comme une sous-séquence, mais je veux connaître les indices de chaînes de chaque sous-séquence, comme je l'ai dit lorsque je regarde les valeurs de la table de recherche. Je sais que la solution réside dans le retour en arrière du conteneur de recherche tabulaire

int count(string a, string b) 
{ 
    int m = a.length(); 
    int n = b.length(); 


    int lookup[m + 1][n + 1] = { { 0 } }; 

    // If first string is empty 
    for (int i = 0; i <= n; ++i) 
     lookup[0][i] = 0; 

    // If second string is empty 
    for (int i = 0; i <= m; ++i) 
     lookup[i][0] = 1; 

    // Fill lookup[][] in bottom up 
    for (int i = 1; i <= m; i++) 
    { 
     for (int j = 1; j <= n; j++) 
     { 
      // we have two options 
      // 
      // 1. consider last characters of both strings 
      // in solution 
      // 2. ignore last character of first string 
      if (a[i - 1] == b[j - 1]) 
       lookup[i][j] = lookup[i - 1][j - 1] + 
           lookup[i - 1][j]; 

      else 
       // If last character are different, ignore 
       // last character of first string 
       lookup[i][j] = lookup[i - 1][j]; 
     } 
    } 

    return lookup[m][n]; 
} 
int main(void){ 
string a = "ccaccbbbaccccca"; 
string b = "abc"; 

cout << count(a, b); 

return 0; 

} 

Answer 1

Vous pouvez le faire récursive (essentiellement, vous aurez juste faire la même chose dans une autre direction):

def gen(i, j): 
    // If there's no match, we're done 
    if lookup[i][j] == 0: 
     return [] 
    // If one of the indices is 0, the answer is an empty list 
    // which means an empty sequence 
    if i == 0 or j == 0: 
     return [[]] 
    // Otherwise, we just do all transitions backwards 
    // combine the results 
    res = [] 
    if a[i - 1] == b[j - 1]: 
     res = gen(i - 1, j - 1) 
     for elem in res: 
       elem.append(a[i - 1]) 
    return res + gen(i - 1, j) 

L'idée est faire exactement la même chose que nous utilisons pour calculer la réponse, mais pour retourner une liste d'indices au lieu du nombre de façons.

Je n'ai pas testé le code ci-dessus, donc il peut contenir des bugs mineurs, mais je pense que l'idée est claire.