7
Dato 2 stringhe s e t. Devo trovare per ogni sottostringa nella distanza di modifica s (distanza Levenshtein) a t. In realtà ho bisogno di sapere per ogni posizione i in s qual è la distanza minima di modifica per tutte le sottostringhe iniziate nella posizione i.Algoritmo per trovare la modifica di tutte le sottostringhe
Ad esempio:
t = "ab"
s = "sdabcb"
E ho bisogno di ottenere qualcosa di simile:
{2,1,0,2,2}
Spiegazione:
1st position:
distance("ab", "sd") = 4 (2*subst)
distance("ab", "sda") = 3(2*delete + insert)
distance("ab", "sdab") = 2 (2 * delete)
distance("ab", "sdabc") = 3 (3 * delete)
distance("ab", "sdabcb") = 4 (4 * delete)
So, minimum is 2
2nd position:
distance("ab", "da") = 2 (delete + insert)
distance("ab", "dab") = 1 (delete)
distance("ab", "dabc") = 2 (2*delete)
....
So, minimum is 1
3th position:
distance("ab", "ab") = 0
...
minimum is 0
e così via.
Posso usare l'algoritmo della forza bruta per risolvere questo compito, ovviamente. Ma c'è un algoritmo più veloce?
Grazie per l'aiuto.
So che la tua risposta '{2,1, ** 0,2 **, 2}' è errata, perché i numeri adiacenti possono differire al massimo da 1: se c'è una sottostringa 's [i..j ] 'con la distanza minima di modifica' k' a 't', quindi la sottostringa' s [(i + 1) .. j] 'può abbinare' t' con costo al massimo 'k + 1' facendo la prima operazione di modifica un inserimento di 's [i]' all'inizio della stringa. Nel tuo esempio, per la quarta posizione, 'distanza (" ab "," b ") = 1' (1 inserto) e per la 5a,' distanza ("ab", "cb") = 1' (1 sottost) . –