Wyrażanie arbitralnej permutacji jako sekwencji operacji (wstawianie, przenoszenie, usuwanie)

Załóżmy, że mam dwa ciągi. Nazywamy je i . Żaden ciąg nie ma powtarzających się znaków.$A$$B$

Jak znaleźć najkrótszą sekwencję operacji wstawiania, przenoszenia i usuwania, która zamienia w , gdzie:$A$$B$

• insert(char, offset)wstawia charna podany offsetw ciągu
• move(from_offset, to_offset)przesuwa postać aktualnie przesuniętą from_offsetdo nowej pozycji, tak aby przesunęła sięto_offset
• delete(offset) usuwa znak z offset

Przykład zastosowania: wykonujesz zapytanie do bazy danych i wyświetlasz wyniki na swojej stronie. Później ponownie uruchom zapytanie bazy danych i odkryjesz, że wyniki uległy zmianie. Chcesz zmienić zawartość strony, aby dopasować ją do zawartości bazy danych, używając minimalnej liczby operacji DOM. Są dwa powody, dla których chcesz mieć najkrótszą sekwencję operacji. Po pierwsze, wydajność. Gdy zmienia się tylko kilka rekordów, musisz upewnić się, że wykonujesz zamiast operacji DOM, ponieważ są one drogie. Po drugie, poprawność. Jeśli element został przeniesiony z jednej pozycji do drugiej, chcesz przenieść powiązane węzły DOM w ramach jednej operacji, bez ich niszczenia i odtwarzania. W przeciwnym razie utracisz stan skupienia, zawartość elementów i tak dalej.$\mathcal{O}(1)$$\mathcal{O}(n)$<input>

Sugeruję przyjrzeć się algorytmowi edycji odległości . Zamiast tylko obliczać odległość, warto zapisać ścieżkę masy minimalnej w tablicy i zwrócić ją.