Załóżmy, że mam dwa ciągi. Nazywamy je i . Żaden ciąg nie ma powtarzających się znaków.
Jak znaleźć najkrótszą sekwencję operacji wstawiania, przenoszenia i usuwania, która zamienia w , gdzie:
insert(char, offset)
wstawiachar
na podanyoffset
w ciągumove(from_offset, to_offset)
przesuwa postać aktualnie przesuniętąfrom_offset
do nowej pozycji, tak aby przesunęła sięto_offset
delete(offset)
usuwa znak zoffset
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.<input>
move
operacji, więc może być konieczne zróżnicowanie interpretacji wyniku.