Алгоритми та структури даних · Middle · Запитання 45 з 75
Що таке найдовша спільна підпослідовність (LCS) двох рядків?
- ✓Правильна відповідь: Найдовша спільна послідовність у порядку, з дозволеними пропусками
- 2Найдовший підрядок, який обидва рядки містять суцільно
- 3Найдовший префікс, з якого починаються обидва рядки
Пояснення
Для "ABCBDAB" і "BDCABA" одна з LCS - "BCBA". Стандартна таблиця DP має O(n × m). LCS лежить в основі інструментів diff.