Sel terisi
Pasangan cocok
Terpanjang sejauh ini

  • Sedang diisi
  • Dibaca
  • Jawaban

Selengkapnya tentang subsekuens bersama terpanjang

Subsekuens bersama terpanjang (LCS)

Huruf apa saja yang dimiliki bersama oleh dua kata, dalam urutan yang sama? Subsekuens bersama terpanjang menjawabnya, dan alat diff, pemeriksa ejaan, serta perbandingan DNA dibangun di atasnya. Ketik dua kata dan lihat tabel huruf-hurufnya terisi, lalu telusuri jawabannya balik dari sudut. Tekan Putar untuk melihat tabel terisi, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Ketik dua kata: kata pertama berjajar ke bawah di sisi tabel, kata kedua di sepanjang bagian atas. Setiap sel berisi panjang subsekuens bersama terpanjang dari huruf-huruf hingga baris dan kolomnya. Di akhir, huruf-hurufnya dibaca balik dari sel kanan bawah. Contoh baru memilih pasangan kata lain. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Ketik dua kata: kata pertama berjajar ke bawah di sisi tabel, kata kedua di sepanjang bagian atas.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
  3. Lihat setiap sel membandingkan dua hurufnya, lalu ikuti jalur oranye balik dari sudut untuk membaca jawabannya.

Cara kerja tabel

Sebuah sel berisi panjang subsekuens bersama terpanjang dari huruf-huruf kata pertama hingga barisnya dan huruf-huruf kata kedua hingga kolomnya. Baris dan kolom bertanda – mewakili kata kosong, jadi nilainya 0. Jika dua huruf sebuah sel sama, nilai sel itu satu lebih besar daripada sel di kiri atasnya. Jika berbeda, salah satu dari dua huruf itu bukan bagian dari jawaban, jadi sel mengambil nilai yang lebih besar antara sel di atas dan sel di kiri.

Membaca balik huruf-hurufnya

Sel kanan bawah adalah panjang jawabannya. Untuk menemukan hurufnya, mulailah dari sana: di tempat dua hurufnya cocok, huruf itu termasuk dalam subsekuens dan langkah berikutnya ke kiri atas; jika tidak, pindah ke sel yang lebih besar antara sel di atas dan sel di kiri. Huruf-huruf yang terkumpul di sepanjang jalan, dibaca terbalik, membentuk sebuah subsekuens bersama terpanjang. Bisa ada yang lain dengan panjang sama; pembacaan balik menemukan salah satunya.

Pertanyaan yang sering diajukan

Apa bedanya subsekuens dan substring?

Substring adalah deretan huruf yang bersebelahan, seperti ACE dalam RACER. Subsekuens menjaga urutan tetapi boleh melewatkan huruf, jadi ACE juga subsekuens dari ABCDE. Substring bersama terpanjang adalah masalah lain dengan tabel yang mirip.

Seberapa cepat algoritma LCS?

Untuk kata sepanjang m dan n, tabelnya punya m·n sel yang masing-masing diisi dalam satu langkah, jadi kerjanya O(m·n). Untuk dua teks berisi 10.000 baris, itu berarti 100 juta sel; karena itulah alat diff memakai metode yang lebih cerdik berdasarkan gagasan yang sama.

Apakah subsekuens bersama terpanjang selalu tunggal?

Tidak. ABCBDAB dan BDCABA punya tiga subsekuens bersama berbeda sepanjang 4: BCBA, BCAB, dan BDAB. Tabel memberikan panjangnya; pembacaan balik memilih salah satunya.

Apakah LCS menunjukkan seberapa mirip dua kata?

Sebagian. Dua kata sepanjang m dan n dengan subsekuens bersama terpanjang sepanjang k dapat diubah satu menjadi yang lain dengan menghapus m − k huruf dan menyisipkan n − k huruf. Jarak edit, yang juga mengizinkan penggantian huruf, sering menjadi ukuran yang lebih baik.

Apakah ada data yang dikirim ke mana pun?

Tidak. Semuanya dihitung di dalam browser, dan pengaturan terakhir tetap tersimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor