- Wypełniana
- Odczytywana
- Odpowiedź
Najdłuższy wspólny podciąg (LCS)
Jakie litery mają wspólne dwa słowa, w tej samej kolejności? Odpowiada na to najdłuższy wspólny podciąg, a opierają się na nim narzędzia diff, sprawdzanie pisowni i porównywanie DNA. Wpisz dwa słowa, zobacz, jak wypełnia się tabela ich liter, a potem odtwórz odpowiedź wstecz od rogu. Naciśnij Odtwórz, aby zobaczyć, jak wypełnia się tabela, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Wpisz dwa słowa: pierwsze biegnie wzdłuż boku tabeli, drugie wzdłuż jej górnej krawędzi. Każda komórka zawiera długość najdłuższego wspólnego podciągu liter aż do jej wiersza i kolumny. Na końcu litery są odczytywane wstecz od prawej dolnej komórki. Nowy przykład wybiera inną parę słów. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Wpisz dwa słowa: pierwsze biegnie wzdłuż boku tabeli, drugie wzdłuż jej górnej krawędzi.
- Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce.
- Zobacz, jak każda komórka porównuje swoje dwie litery, a potem podążaj pomarańczową ścieżką wstecz od rogu, aby odczytać odpowiedź.
Jak działa tabela
Komórka zawiera długość najdłuższego wspólnego podciągu liter pierwszego słowa aż do jej wiersza i liter drugiego słowa aż do jej kolumny. Wiersz i kolumna oznaczone – odpowiadają pustemu słowu, więc mają wartość 0. Jeśli dwie litery komórki są równe, komórka jest o jeden większa od komórki na ukos w lewo w górę. Jeśli się różnią, jedna z dwóch liter nie należy do odpowiedzi, więc komórka bierze większą z wartości komórki powyżej i komórki po lewej.
Odczytywanie liter wstecz
Prawa dolna komórka to długość odpowiedzi. Aby znaleźć litery, zacznij od niej: tam, gdzie dwie litery pasują, ta litera należy do podciągu i przechodzisz na ukos w lewo w górę; w przeciwnym razie przechodzisz do większej z komórek powyżej i po lewej. Litery zebrane po drodze, czytane od końca, tworzą najdłuższy wspólny podciąg. Mogą istnieć inne tej samej długości; odczyt wstecz znajduje jeden z nich.
Często zadawane pytania
Czym różni się podciąg od podsłowa?
Podsłowo to ciąg liter stojących bezpośrednio obok siebie, jak ACE w RACER. Podciąg zachowuje kolejność, ale może pomijać litery, więc ACE jest też podciągiem ABCDE. Najdłuższe wspólne podsłowo to inny problem, z podobną tabelą.
Jak szybki jest algorytm LCS?
Dla słów o długościach m i n tabela ma m·n komórek, a każda jest wypełniana w jednym kroku, więc praca wynosi O(m·n). Dla dwóch tekstów po 10 000 wierszy to 100 milionów komórek, dlatego narzędzia diff używają sprytniejszych metod opartych na tej samej idei.
Czy najdłuższy wspólny podciąg jest jednoznaczny?
Nie. ABCBDAB i BDCABA mają trzy różne wspólne podciągi długości 4: BCBA, BCAB i BDAB. Tabela podaje długość; odczyt wstecz wybiera jeden z nich.
Czy LCS mówi, jak podobne są dwa słowa?
Częściowo. Dwa słowa o długościach m i n, których najdłuższy wspólny podciąg ma długość k, można przekształcić jedno w drugie, usuwając m − k liter i wstawiając n − k. Odległość edycyjna, która pozwala też zamienić literę, jest często lepszą miarą.
Czy cokolwiek jest gdzieś wysyłane?
Nie. Wszystko jest obliczane w twojej przeglądarce, a twoje ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora