- Dolduruluyor
- Okunan
- Cevap
En uzun ortak alt dizi (LCS)
İki kelimede hangi harfler aynı sırayla ortaktır? En uzun ortak alt dizi bu soruyu cevaplar; diff araçları, yazım denetleyicileri ve DNA karşılaştırmaları onun üzerine kuruludur. İki kelime yazın, harflerinden oluşan bir tablonun dolmasını izleyin, ardından cevabı köşeden geriye doğru takip edin. Tablonun dolmasını izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. İki kelime yazın: birincisi tablonun yanında yukarıdan aşağı, ikincisi üst kenar boyunca dizilir. Her hücre, satırına ve sütununa kadar olan harflerin en uzun ortak alt dizisinin uzunluğunu tutar. Sonunda harfler sağ alt hücreden geriye doğru okunur. Yeni örnek başka bir kelime çifti seçer. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- İki kelime yazın: birincisi tablonun yanında yukarıdan aşağı, ikincisi üst kenar boyunca dizilir.
- Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
- Her hücrenin iki harfini karşılaştırmasını izleyin, ardından cevabı okumak için turuncu yolu köşeden geriye doğru takip edin.
Tablo nasıl çalışır?
Bir hücre, birinci kelimenin satırına kadar olan harfleriyle ikinci kelimenin sütununa kadar olan harflerinin en uzun ortak alt dizisinin uzunluğunu tutar. – ile işaretli satır ve sütun boş bir kelimeyi temsil eder, bu yüzden değerleri 0'dır. Hücrenin iki harfi eşitse hücre, sol üst çaprazındaki hücreden bir fazladır. Farklıysa iki harften biri cevabın parçası değildir, bu yüzden hücre üstteki ve soldaki hücrelerden büyük olanı alır.
Harfleri geriye doğru okumak
Sağ alt hücre cevabın uzunluğudur. Harfleri bulmak için oradan başlayın: iki harfin eşleştiği yerde o harf alt dizidedir ve sol üst çapraza geçilir; aksi hâlde üstteki ve soldaki hücrelerden büyük olanına geçilir. Yol boyunca toplanan harfler ters sırayla okunduğunda en uzun ortak alt dizilerden birini verir. Aynı uzunlukta başkaları da olabilir; geriye okuma bunlardan birini bulur.
Sık sorulan sorular
Alt dizi ile alt dize arasındaki fark nedir?
Alt dize, RACER içindeki ACE gibi yan yana duran harflerden oluşur. Alt dizi sırayı korur ama harf atlayabilir; bu yüzden ACE aynı zamanda ABCDE'nin de bir alt dizisidir. En uzun ortak alt dize, benzer bir tabloyla çözülen farklı bir problemdir.
LCS algoritması ne kadar hızlıdır?
m ve n uzunluğundaki kelimeler için tabloda m·n hücre vardır ve her biri tek adımda dolar, yani iş O(m·n)'dir. 10.000 satırlık iki metin için bu 100 milyon hücre eder; diff araçlarının aynı fikre dayanan daha akıllıca yöntemler kullanmasının nedeni budur.
En uzun ortak alt dizi tek midir?
Hayır. ABCBDAB ile BDCABA'nın 4 uzunluğunda üç farklı ortak alt dizisi vardır: BCBA, BCAB ve BDAB. Tablo uzunluğu verir; geriye okuma bunlardan birini seçer.
LCS iki kelimenin ne kadar benzer olduğunu gösterir mi?
Kısmen. m ve n uzunluğunda, en uzun ortak alt dizisi k uzunluğunda olan iki kelime, m − k harf silinip n − k harf eklenerek birbirine dönüştürülebilir. Bir harfi değiştirmeye de izin veren düzenleme mesafesi çoğu zaman daha iyi bir ölçüdür.
Herhangi bir veri bir yere gönderiliyor mu?
Hayır. Her şey tarayıcınızda hesaplanır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git