- Wordt gevuld
- Wordt gelezen
- Antwoord
Langste gemeenschappelijke deelrij (LCS)
Welke letters hebben twee woorden gemeen, in dezelfde volgorde? De langste gemeenschappelijke deelrij geeft daar antwoord op, en diff-programma's, spellingcontroles en DNA-vergelijkingen bouwen erop voort. Typ twee woorden, zie een tabel van hun letters vollopen en volg dan het antwoord terug vanuit de hoek. Druk op Afspelen om de tabel te zien vollopen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Typ twee woorden: het eerste staat langs de zijkant van de tabel, het tweede langs de bovenkant. Elke cel bevat de lengte van de langste gemeenschappelijke deelrij van de letters tot en met zijn rij en kolom. Aan het eind worden de letters teruggelezen vanaf de cel rechtsonder. Nieuw voorbeeld kiest een ander paar woorden. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.
Hoe het werkt
- Typ twee woorden: het eerste staat langs de zijkant van de tabel, het tweede langs de bovenkant.
- Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
- Zie hoe elke cel zijn twee letters vergelijkt en volg dan het oranje pad terug vanuit de hoek om het antwoord te lezen.
Hoe de tabel werkt
Een cel bevat de lengte van de langste gemeenschappelijke deelrij van de letters van het eerste woord tot en met zijn rij en de letters van het tweede woord tot en met zijn kolom. De rij en de kolom gemarkeerd met – staan voor een leeg woord, dus zijn ze 0. Als de twee letters van een cel gelijk zijn, is de cel één meer dan de cel linksboven. Als ze verschillen, hoort een van de twee letters niet bij het antwoord, dus neemt de cel de grootste van de cel erboven en de cel links.
De letters teruglezen
De cel rechtsonder is de lengte van het antwoord. Om de letters te vinden begin je daar: waar de twee letters overeenkomen, hoort die letter bij de deelrij en ga je naar linksboven; anders ga je naar de grootste van de cel erboven en de cel links. De letters die je onderweg verzamelt, achterstevoren gelezen, vormen een langste gemeenschappelijke deelrij. Er kunnen andere van dezelfde lengte zijn; het teruglezen vindt er één.
Veelgestelde vragen
Wat is het verschil tussen een deelrij en een deelstring?
Een deelstring is een reeks letters die direct naast elkaar staan, zoals ACE in RACER. Een deelrij houdt de volgorde aan maar mag letters overslaan, dus ACE is ook een deelrij van ABCDE. De langste gemeenschappelijke deelstring is een ander probleem met een vergelijkbare tabel.
Hoe snel is het LCS-algoritme?
Voor woorden met lengtes m en n heeft de tabel m·n cellen, die elk in één stap gevuld worden, dus het werk is O(m·n). Voor twee teksten van 10.000 regels zijn dat 100 miljoen cellen; daarom gebruiken diff-programma's slimmere methoden die op hetzelfde idee voortbouwen.
Is de langste gemeenschappelijke deelrij uniek?
Nee. ABCBDAB en BDCABA hebben drie verschillende gemeenschappelijke deelrijen van lengte 4: BCBA, BCAB en BDAB. De tabel geeft de lengte; het teruglezen kiest er één.
Zegt de LCS hoe sterk twee woorden op elkaar lijken?
Gedeeltelijk. Twee woorden met lengtes m en n en een langste gemeenschappelijke deelrij van lengte k kun je in elkaar omzetten door m − k letters te verwijderen en n − k letters in te voegen. De bewerkingsafstand, die ook het vervangen van een letter toestaat, is vaak een betere maat.
Wordt er iets verstuurd?
Nee. Alles wordt in je browser berekend, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor