- Se completează
- Citită
- Răspuns
Cel mai lung subșir comun (LCS)
Ce litere au în comun două cuvinte, în aceeași ordine? Cel mai lung subșir comun răspunde la această întrebare, iar instrumentele diff, corectoarele ortografice și comparațiile de ADN se bazează pe el. Scrieți două cuvinte, urmăriți cum se completează un tabel cu literele lor, apoi refaceți drumul spre răspuns pornind din colț. Apăsați Redare pentru a urmări cum se completează tabelul sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Scrieți două cuvinte: primul se așază de-a lungul laturii tabelului, al doilea de-a lungul marginii de sus. Fiecare celulă conține lungimea celui mai lung subșir comun al literelor până la rândul și coloana ei. La final, literele sunt citite înapoi pornind din celula din dreapta jos. Exemplu nou alege o altă pereche de cuvinte. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Scrieți două cuvinte: primul se așază de-a lungul laturii tabelului, al doilea de-a lungul marginii de sus.
- Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde.
- Urmăriți cum fiecare celulă își compară cele două litere, apoi urmați drumul portocaliu înapoi din colț pentru a citi răspunsul.
Cum funcționează tabelul
O celulă conține lungimea celui mai lung subșir comun dintre literele primului cuvânt până la rândul ei și literele celui de-al doilea cuvânt până la coloana ei. Rândul și coloana marcate cu – reprezintă un cuvânt gol, deci sunt 0. Dacă cele două litere ale unei celule sunt egale, celula are cu unu mai mult decât celula din stânga sus. Dacă diferă, una dintre cele două litere nu face parte din răspuns, așa că celula ia valoarea mai mare dintre celula de deasupra și celula din stânga.
Citirea înapoi a literelor
Celula din dreapta jos este lungimea răspunsului. Pentru a găsi literele, începeți de acolo: unde cele două litere se potrivesc, acea literă face parte din subșir și vă mutați în stânga sus; altfel vă mutați la cea mai mare dintre celula de deasupra și celula din stânga. Literele adunate pe drum, citite invers, formează un cel mai lung subșir comun. Pot exista și altele de aceeași lungime; citirea înapoi îl găsește pe unul dintre ele.
Întrebări frecvente
Care este diferența dintre un subșir și o subsecvență?
O subsecvență este un șir de litere aflate una lângă alta, ca ACE în RACER. Un subșir păstrează ordinea, dar poate sări peste litere, așa că ACE este și un subșir al lui ABCDE. Cea mai lungă subsecvență comună este o altă problemă, cu un tabel asemănător.
Cât de rapid este algoritmul LCS?
Pentru cuvinte de lungimi m și n, tabelul are m·n celule, fiecare completată într-un pas, deci efortul este O(m·n). Pentru două texte de 10.000 de linii, asta înseamnă 100 de milioane de celule, motiv pentru care instrumentele diff folosesc metode mai ingenioase, bazate pe aceeași idee.
Este cel mai lung subșir comun unic?
Nu. ABCBDAB și BDCABA au trei subșiruri comune diferite de lungime 4: BCBA, BCAB și BDAB. Tabelul dă lungimea; citirea înapoi îl alege pe unul dintre ele.
Arată LCS cât de asemănătoare sunt două cuvinte?
În parte. Două cuvinte de lungimi m și n, al căror cel mai lung subșir comun are lungimea k, pot fi transformate unul în celălalt ștergând m − k litere și inserând n − k. Distanța de editare, care permite și înlocuirea unei litere, este adesea o măsură mai bună.
Se trimite ceva undeva?
Nu. Totul este calculat în browserul dumneavoastră, iar ultimele setări rămân în spațiul de stocare local al acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor