Longest Common Subsequence

Q: Berapa kompleksitas waktu dari Longest Common Subsequence?

Solusi tabel berjalan dalam waktu O(n × m) , satu sel untuk setiap pasangan prefiks. Solusi ini membutuhkan memori O(n × m) untuk tabel lengkap, atau O(min(n, m)) dengan dua baris. Rekursi biasa tanpa tabel membutuhkan waktu eksponensial.

SedangDynamic programming

+10

Kamu mendapatkan dua string, text1 dan text2. Subsekuens dari sebuah string mempertahankan beberapa hurufnya dalam urutan aslinya dan membuang sisanya; huruf yang dipertahankan tidak harus bersebelahan. Kembalikan panjang string terpanjang yang merupakan subsekuens dari keduanya, atau 0 jika kedua string tidak memiliki huruf yang sama.

Fungsi

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: string pertama
text2string: string kedua
Mengembalikaninteger: panjang subsekuens umum terpanjang

Batasan

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Kedua string hanya berisi huruf kecil bahasa Inggris.

Contoh

Input: text1 = "stone"text2 = "longest"
Output: 3
Penjelasan: o, n, e muncul dalam urutan ini di kedua kata, jadi one sama, dengan panjang 3. Huruf s dan t muncul terakhir di longest, tetapi pertama di stone, jadi menggunakannya menghasilkan paling banyak st.

Input: text1 = "pear"text2 = "reap"
Output: 2
Penjelasan: ea muncul di kedua kata. Huruf p dan r berada di sisi yang berlawanan dari ea pada kedua kata, sehingga tidak ada yang bisa bergabung dengannya, dan jawabannya adalah 2.

Pertanyaan lanjutan

Bisakah kamu mengembalikan satu subsekuens umum terpanjang itu sendiri, beserta panjangnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Pencocokan greedy gagal: memasangkan c dari cab dengan c terakhir dari abc tidak menyisakan apa pun untuk a dan b; melewatkannya akan menemukan ab. Jawaban untuk dua prefiks bergantung pada jawaban untuk prefiks yang lebih pendek, jadi tabel (n+1) × (m+1) menyelesaikan setiap pasangan satu kali. Setiap baris hanya membaca baris di atasnya, jadi dua baris sudah cukup.

Bandingkan huruf pertama dengan rekursi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Misalkan lcs(i, j) adalah jawaban untuk akhiran text1[i:] dan text2[j:]. Jika huruf pertamanya sama, pasangkan keduanya: subsekuens bersama terpanjang yang melewatkan pasangan ini dapat mengganti pasangan pertamanya dengan pasangan ini tanpa menjadi lebih pendek. Jadi, jawabannya adalah 1 + lcs(i+1, j+1).

Jika hurufnya berbeda, keduanya tidak dapat digunakan sekaligus karena pasangannya akan saling menyilang. Jadi, salah satunya dapat dihilangkan: max(lcs(i+1, j), lcs(i, j+1)). Akhiran kosong menghasilkan 0.

Setiap ketidakcocokan memulai dua pemanggilan. Dua string 20 huruf tanpa huruf yang sama membutuhkan sekitar 2.8 × 10^11 pemanggilan, padahal hanya ada (n+1) × (m+1) pasangan berbeda (i, j), jadi hampir setiap pemanggilan mengulangi pemanggilan sebelumnya.

Algoritma

Tulis lcs(i, j) untuk sufiks yang dimulai pada i dan j.
Jika i atau j melewati akhir string-nya, kembalikan 0.
Jika text1[i] == text2[j], kembalikan 1 + lcs(i+1, j+1).
Jika tidak, kembalikan max(lcs(i+1, j), lcs(i, j+1)).
Jawabannya adalah lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Isi tabel prefiks

Intuisi

Misalkan dp[i][j] adalah jawaban untuk i huruf pertama dari text1 dan j huruf pertama dari text2, jadi indeks 0 berarti prefiks kosong dan baris 0 serta kolom 0 bernilai 0. Bandingkan huruf terakhir dari kedua prefiks, text1[i-1] dan text2[j-1]: huruf yang sama dipasangkan, dp[i-1][j-1] + 1; huruf yang berbeda, salah satunya diabaikan, max(dp[i-1][j], dp[i][j-1]). Ini adalah rekursi yang dibaca dari akhir.

Setiap sel membaca sel di atas, di sebelah kiri, serta diagonal atas-kiri, jadi mengisi baris demi baris dari kiri ke kanan akan selalu menemukan sel-sel tersebut sudah siap. Untuk pear dan reap, baris untuk pea adalah [0, 0, 1, 2, 2]; selnya untuk rea bernilai 2 karena a cocok dengan a, sehingga menambahkan satu pada sel untuk pe dan re.

Dua string yang masing-masing terdiri dari 1000 huruf memerlukan sekitar 10^6 langkah dengan waktu konstan.

Algoritma

Buat tabel dp berisi nol sebanyak (n+1) × (m+1).
Untuk i dari 1 hingga n dan j dari 1 hingga m, bandingkan text1[i-1] dengan text2[j-1].
Jika cocok, tetapkan dp[i][j] = dp[i-1][j-1] + 1.
Jika tidak, tetapkan dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Kembalikan dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Hanya pertahankan dua baris

Intuisi

Setelah satu baris selesai, baris-baris di atasnya tidak pernah dibaca lagi. Simpan prev untuk baris yang sudah selesai dan cur untuk baris yang sedang diisi, lalu tukar keduanya setelah setiap baris. Relasi rekurens dan urutannya tetap sama.

Jawabannya tidak bergantung pada string mana yang muncul lebih dulu, jadi buat baris-barisnya mengikuti string yang lebih pendek. Setiap baris kemudian menyimpan min(n, m) + 1 angka: 1001, bukan sejuta sel untuk input terbesar, dengan jumlah langkah yang sama, yaitu 10^6.

Algoritma

Jika text2 lebih panjang daripada text1, tukar keduanya.
Buat prev dan cur, masing-masing berisi m + 1 angka nol, dengan m sebagai panjang yang lebih pendek.
Untuk setiap huruf text1, isi cur[1..m] dengan aturan yang sama seperti pada tabel, dengan membaca prev untuk baris di atasnya.
Tukar prev dan cur.
Kembalikan prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Jebakan dan kasus tepi

Mencampur indeks tabel dengan indeks string. Sel dp[i][j] membandingkan text1[i-1] dengan text2[j-1], karena baris 0 adalah prefiks kosong.
Saat cocok, menambahkan satu ke max(dp[i-1][j], dp[i][j-1]), bukan ke dp[i-1][j-1]. Ini bisa menggunakan satu huruf dua kali: aa dibandingkan dengan a akan menghasilkan 2, bukan 1.
Menulis ke baris yang masih kamu baca. Dengan dua baris, setiap nilai dari baris di atas harus berasal dari prev, dan cur[0] harus tetap 0.
Menyimpan rekursi dalam memo di Python untuk string sepanjang 1000 huruf. Kedalaman pemanggilan mencapai 2000, melebihi batas default 1000.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Longest Common Subsequence?

Solusi tabel berjalan dalam waktu O(n × m), satu sel untuk setiap pasangan prefiks. Solusi ini membutuhkan memori O(n × m) untuk tabel lengkap, atau O(min(n, m)) dengan dua baris. Rekursi biasa tanpa tabel membutuhkan waktu eksponensial.

Apa perbedaan antara subsekuens umum terpanjang dan substring umum terpanjang?

Subsekuens dapat melewati huruf asalkan urutannya tetap dipertahankan; substring adalah rangkaian huruf yang berdekatan. Untuk stone dan longest, subsekuens umum terpanjang adalah one (3), tetapi substring umum terpanjang adalah on (2). Tabel substring mengatur ulang sebuah sel menjadi 0 saat terjadi ketidakcocokan, alih-alih menyalin nilai dari sel tetangga.

Bagaimana hubungan LCS dengan alat diff dan jarak edit?

Diff antara dua versi file mempertahankan subsekuens umum terpanjang dari baris-barisnya dan menampilkan setiap baris lainnya sebagai ditambahkan atau dihapus. Jumlah penyisipan dan penghapusan paling sedikit yang mengubah satu string menjadi string lainnya adalah n + m - 2 × LCS. Jarak edit juga memungkinkan penggantian huruf, jadi diperlukan tabel tersendiri.

def longestCommonSubsequence(text1, text2):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

text1 = "stone"
text2 = "longest"

Output yang diharapkan

Longest Common Subsequence

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Bandingkan huruf pertama dengan rekursi

Isi tabel prefiks

Hanya pertahankan dua baris

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa