Algorytmy i struktury danych · Middle · Pytanie 45 z 75
Czym jest najdłuższy wspólny podciąg (LCS) dwóch napisów?
- ✓Poprawna odpowiedź: Najdłuższym wspólnym ciągiem w kolejności, z dozwolonymi przerwami
- 2Najdłuższym podnapisem, który oba napisy zawierają w całości
- 3Najdłuższym prefiksem, od którego zaczynają się oba napisy
Wyjaśnienie
Dla "ABCBDAB" i "BDCABA" jednym z LCS jest "BCBA". Standardowa tabela DP ma O(n × m). LCS to idea stojąca za narzędziami diff.