Algoritmo di Hirschberg

L'algoritmo di Hirschberg, dal nome del suo creatore, Dan Hirschberg, è un algoritmo di programmazione dinamica che trova l'allineamento ottimale della sequenza tra due stringhe. L'ottimalità si misura con la distanza di Levenshtein, definita come la somma dei costi di inserimenti, sostituzioni, eliminazioni e azioni nulle necessarie per cambiare una stringa nell'altra. L'algoritmo di Hirschberg è semplicemente descritto come una versione più efficiente in termini di spazio dell'algoritmo Needleman-Wunsch che utilizza divide et impera. L'algoritmo di Hirschberg è comunemente usato nella biologia computazionale per trovare il numero massimo di allineamenti globali di DNA e sequenze proteiche.