Nombre minimum de répétitions dans un tableau combiné de caractères

Question

Supposons que j'ai deux tableaux et que je veux les fusionner de sorte que le tableau fusionné ait le minimum de répétitions. Par exemple, [ 'x' , 'x' ] est une répétition.

arr1 = [ 'x' , 'd' , 'd' , 'm' , 'f' , 'm' ]
arr2 = [ 'd' , 'd' , 'x' , 'f' , 'f' , 'm' ]

La seule condition est que dans le tableau fusionné, les éléments de arr1 et de arr2 doivent apparaître dans leurs ordres respectifs à l'intérieur de arr1 et arr2. Voici un exemple du tableau fusionné avec 0 répétition tout en respectant cette condition.

merged = [ 'd' , 'x' , 'd' , 'x' , 'd' , 'f' , 'd' , 'm' , 'f' , 'm' , 'f' , 'm' ]

J'essaie de lier ce problème à des problèmes de programmation dynamique populaires pour m'aider. Y a-t-il des problèmes similaires sur lesquels je devrais me pencher ?

Answer 1

Je définis la fonction suivante: F(d, i, j) = le nombre minimum de répétitions possible à partir d'une chaîne composée d'un préfixe de arr1 de longueur i et d'un préfixe de arr2 de longueur j, suivi d'un symbole ith (d=0) ou jth (d=1) de arr[d]. Ainsi, F(d, i, j) correspond à une chaîne de longueur i+j+1.

Si vous êtes familier avec la manière dont la distance de Levenshtein est calculée, pensez-y comme au lieu d'attribuer des scores aux sommets de la grille, nous attribuons des scores aux arêtes, où d signifie s'il s'agit de l'arête horizontale ou verticale. Cela nous donne une 'mémoire' d'un symbole, nous pouvons donc détecter les répétitions.

Le code C++ suivant calcule le nombre minimum de répétitions et imprime une chaîne correspondante en temps quadratique:

#include 
#include 
#include 
#include 

char A[32], B[32], C[64];
int score[2][32][32];

void print_result(int d, int i, int j)
{
    char c = d ? B[j] : A[i];
    int s0 = i > 0 ? score[0][i-1][j] + (A[i-1] == c) : INT_MAX;
    int s1 = j > 0 ? score[1][i][j-1] + (B[j-1] == c) : INT_MAX;

    if(s0 <= s1 && i > 0)
        print_result(0, i-1, j);
    else if(j > 0)
        print_result(1, i, j-1);

    printf("%c", c);
}

void print_result(int i, int j)
{
    if(score[0][i-1][j] < score[1][i][j-1])
        print_result(0, i-1, j);
    else
        print_result(1, i, j-1);
}

int main()
{
    fgets(A, sizeof(A), stdin);
    fgets(B, sizeof(B), stdin);

    int m = strlen(A) - 1; // -1 to remove LF
    int n = strlen(B) - 1;

    for(int j = 0; j <= n; ++j)
    {
        for(int i = 0; i <= m; ++i)
        {
            score[0][i][j] = !i && !j ? 0 : std::min(
                i > 0 ? score[0][i-1][j] + (A[i-1] == A[i]) : INT_MAX,
                j > 0 ? score[1][i][j-1] + (B[j-1] == A[i]) : INT_MAX
            );
            score[1][i][j] = !i && !j ? 0 : std::min(
                i > 0 ? score[0][i-1][j] + (A[i-1] == B[j]) : INT_MAX,
                j > 0 ? score[1][i][j-1] + (B[j-1] == B[j]) : INT_MAX
            );
        }
    }

    printf("répétitions : %d\n", std::min(score[0][m-1][n], score[1][m][n-1]));

    print_result(m, n);
    printf("\n");

    return 0;
}