Um zwei Viren zu vergleichen wird zunächst jeweils ihr Genom als String über dem Alphabet $\Sigma = \{A,T,G,C\}$ dargestellt. Gegeben zwei solcher Strings (die eventuell auch unterschiedlich lang sind) möchte man nun wissen, wie viele Lösch-, Einfüge- oder Ersetzungsschritte man benötigt, um einen String in den anderen umzuwandeln. Zum Beispiel (mit einem anderen Alphabet, um es anschaulicher zu machen):
$$
\mathrm{ella} \rightarrow \mathrm{lla} \rightarrow \mathrm{llar} \rightarrow \mathrm{lar} \rightarrow \mathrm{lars}
$$
Es hat also vier Schritte benötigt, schneller wäre es auch nicht gegangen. Entwickle einen Algorithmus (der nicht $n^n$ oder so Möglichkeiten durchtestet), welcher die Anzahl Schritte bestimmt, mit denen man von einem gegebenen DNS-String (der Länge) zu einem gegebenen anderen DNS-String (der Länge $m$) kommen kann.
