Dynamic ProgrammingMenengahFase D–FE1E5

Longest Common Subsequence

LCS mencari deret huruf terpanjang yang muncul di dua teks dengan urutan yang sama (boleh diselang-seling). Sebuah tabel dinamis diisi: bila dua huruf cocok, nilainya = diagonal kiri-atas + 1; bila beda, ambil yang terbesar dari atas atau kiri. Menelusuri balik tabel memberi deret bersama itu. Inilah inti dari membandingkan dua versi teks. Visualisasi mengisi tabel dan menyorot sel-sel yang cocok.

Example use case

Fitur git diff yang menandai perbedaan dua versi kode, dan alat pendeteksi plagiat yang mencari bagian yang sama antara dua dokumen.

Syllabus

Isi tabel: huruf cocok = diagonal+1, huruf beda = max(atas, kiri); telusuri balik untuk deret bersamanya.

Objectives

·Memahami pemrograman dinamis pada dua dimensi
·Menjelaskan aturan sel cocok vs sel beda
·Menelusuri balik solusi dari tabel yang sudah terisi

How It Works

·Buat tabel (panjang X+1) × (panjang Y+1) berisi 0.
·Untuk tiap pasang huruf: bila SAMA, sel = diagonal kiri-atas + 1.
·Bila BEDA, sel = nilai terbesar dari atas atau kiri.
·Telusuri balik dari pojok kanan-bawah — huruf-huruf cocok menyusun LCS.

Prerequisites

·Konsep subsequence (deret bagian berurutan)
·Tabel atau grid dua dimensi
·Rekursi / DP dasar

Real-World Uses

·git diff membandingkan dua versi kode.
·Deteksi plagiat dan kemiripan dokumen.
·Menyelaraskan urutan DNA di bioinformatika.

Complexity O(panjang X × panjang Y)