Алгоритми та структури даних · Senior · Запитання 36 з 75
Який алгоритм за замовчуванням використовують git diff і багато diff-інструментів?
- 1Алгоритм Дейкстри на графі рядків
- 2Відстань Левенштейна, пораховану посимвольно
- ✓Правильна відповідь: Алгоритм Маєрса на основі найкоротшого сценарію редагування
Пояснення
Маєрс знаходить найкоротшу послідовність вставок і видалень за O((n + m) × d), де d - кількість відмінностей, тож схожі файли порівнюються швидко. Він тісно пов'язаний із найдовшою спільною підпослідовністю.