Longest Common Substring

Q: Apa kompleksitas waktu untuk substring umum terpanjang?

Solusi pemrograman dinamis membutuhkan waktu O(n × m) , dan memori O(m) dengan satu baris. Memperluas dari setiap pasangan titik awal membutuhkan O(n × m × min(n, m)) dalam kasus terburuk. Automaton sufiks mencapai sekitar O(n + m) , dengan biaya program yang jauh lebih panjang.

Q: Bagaimana cara mengembalikan substring terpanjang yang sama?

Setiap kali sebuah sel memiliki nilai lebih besar daripada best , catat juga posisi i di s1 tempat blok tersebut berakhir. Pada akhirnya, substring tersebut adalah huruf-huruf best dari s1 yang berakhir di posisi itu. Perbandingan lebih besar yang ketat membuat blok terpanjang pertama yang ditemukan di s1 tetap dipilih.

SedangDynamic programming

+10

Kamu mendapatkan dua string, s1 dan s2. Substring adalah rangkaian huruf berurutan yang diambil dari sebuah string, seperti ork dari clockwork. Temukan substring terpanjang yang sama-sama dimiliki s1 dan s2, lalu kembalikan panjangnya. Jika tidak ada huruf yang muncul di kedua string, jawabannya adalah 0.

Fungsi

longestCommonSubstring(s1: string, s2: string) → integer

s1string: string pertama
s2string: string kedua
Mengembalikaninteger: panjang blok huruf terpanjang yang ditemukan di kedua string

Batasan

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 dan s2 terdiri dari huruf kecil bahasa Inggris.

Contoh

Input: s1 = "clockwork"s2 = "workshop"
Output: 4
Penjelasan: work menutup clockwork dan membuka workshop, jadi ini adalah substring umum dengan panjang 4, dan tidak ada rangkaian yang lebih panjang yang muncul pada keduanya.

Input: s1 = "hammer"s2 = "harmed"
Output: 2
Penjelasan: ha dan me muncul pada kedua kata, tetapi tidak ada rangkaian tiga huruf. Kedua kata memuat h, a, m, e dalam urutan tersebut, tetapi harmed memiliki r di antara a dan m.

Pertanyaan lanjutan

Bisakah kamu menguji apakah ada substring umum dengan panjang tertentu L dalam waktu sekitar O(n + m) menggunakan rolling hash, lalu melakukan pencarian biner pada L?

Petunjuk

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

0 dari 3 dibuka

Solusi

Memperpanjang kecocokan dari setiap pasangan titik awal akan membaca ulang huruf yang sama. Perhatikan bagian tempat sebuah blok berakhir: blok umum yang berakhir pada s1[i] dan s2[j] satu huruf lebih panjang daripada blok yang berakhir pada dua huruf sebelumnya, atau kosong jika hurufnya berbeda. Tabel panjang ini memberikan jawaban dalam waktu O(n × m).

Perluas dari setiap pasangan posisi awal

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Setiap substring umum dimulai pada posisi i di s1 dan posisi j di s2. Untuk setiap pasangan, telusuri ke depan selama huruf-hurufnya cocok dan hitung langkahnya. Jumlah terbesar adalah jawabannya.

Teks yang berulang membuat penelusuran menjadi panjang. Jika kedua string terdiri dari 1000 salinan a, setiap pasangan ditelusuri hingga akhir sufiks yang lebih pendek: sekitar 3.3 × 10^8 perbandingan huruf. Penelusuran dari (i, j) mengulangi seluruh penelusuran dari (i+1, j+1), satu huruf lebih lanjut.

Algoritma

Tetapkan best = 0.
Untuk setiap i di s1 dan setiap j di s2, tetapkan k = 0.
Selama i+k dan j+k berada di dalam string masing-masing, dan s1[i+k] == s2[j+k], tambahkan 1 ke k.
Simpan nilai k terbesar di best, lalu kembalikan nilainya.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Tabel panjang blok yang berakhir pada setiap pasangan

Intuisi

Misalkan run[i][j] adalah panjang blok bersama terpanjang yang berakhir tepat di s1[i-1] dan s2[j-1]; baris 0 dan kolom 0 berisi 0. Blok seperti ini harus memuat kedua huruf. Jika keduanya berbeda, tidak ada blok dan sel tersebut bernilai 0. Jika keduanya sama, blok ini terdiri dari pasangan tersebut ditambah blok yang berakhir satu huruf lebih awal di kedua string: run[i-1][j-1] + 1. Setiap substring bersama berakhir di suatu tempat, jadi jawabannya adalah sel terbesar, di mana pun letaknya.

Untuk hammer dan harmed, huruf h menghasilkan 1 dan huruf a memperpanjangnya menjadi 2, lalu huruf r memutus blok. Huruf m kedua dari hammer bertemu dengan huruf m dari harmed setelah ketidakcocokan antara m dan r, jadi nilainya dimulai dari 1, lalu huruf e menaikkannya menjadi 2. Tidak ada sel yang mencapai 3.

Satu perbandingan untuk setiap sel: sekitar satu juta untuk dua string yang masing-masing memiliki 1000 huruf, apa pun teksnya.

Algoritma

Alokasikan run dengan n+1 baris dan m+1 kolom, semuanya 0, lalu tetapkan best = 0.
Lakukan perulangan i dari 1..n dan, di dalamnya, j dari 1..m, dengan membandingkan s1[i-1] dengan s2[j-1].
Jika cocok, tetapkan run[i][j] = run[i-1][j-1] + 1 dan perbarui best.
Jika tidak cocok, biarkan sel tersebut bernilai 0.
Kembalikan best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Satu baris, diperbarui dari kanan ke kiri

Intuisi

Setiap sel hanya membaca sel yang berada diagonal ke atas dan ke kiri. Jadi, satu array run yang berisi m+1 angka dapat menyimpan tabel jika kamu mengunjungi j dari kanan ke kiri: saat kamu menulis run[j], slot run[j-1] masih menyimpan nilai untuk huruf sebelumnya dari s1, yaitu sel diagonal.

Ketidakcocokan sekarang harus menulis 0 secara eksplisit, karena slot tersebut masih menyimpan angka dari baris sebelumnya. Waktunya tetap O(n × m), dan penggunaan memorinya turun dari sekitar 10^6 angka menjadi 1001.

Algoritma

Buat array run dengan m+1 nilai nol dan tetapkan best = 0.
Untuk setiap huruf ch dari s1, kunjungi j dari m hingga 1.
Jika ch == s2[j-1], tetapkan run[j] = run[j-1] + 1 dan perbarui best.
Jika tidak, tetapkan run[j] = 0.
Kembalikan best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Jebakan dan kasus tepi

Mengembalikan sel terakhir. run[n][m] hanya mencakup blok yang berakhir pada huruf terakhir kedua string. Untuk abc dan abd, nilainya 0, sedangkan ab menghasilkan 2.
Menyalin nilai tetangga yang lebih besar saat ada ketidakcocokan. Itulah aturan subsekuens, dan aturan ini memungkinkan sebuah blok melewati huruf: untuk hammer dan harmed, hasilnya 4, bukan 2.
Menelusuri satu baris dari kiri ke kanan. Nilai diagonal ditimpa sebelum dibaca, sehingga a dibandingkan dengan aa menghasilkan 2.
Melewatkan pengaturan ulang pada satu baris. Panjang dari huruf sebelumnya pada s1 tetap tersimpan dan kemudian memperpanjang blok yang sebenarnya tidak ada.
Menelusuri brute force tanpa memeriksa batas. Untuk zzzz dibandingkan dengan zz, program membaca melewati akhir string yang lebih pendek.

Pertanyaan yang sering diajukan3

Apa perbedaan antara substring umum terpanjang dan subsekuens umum terpanjang?

Substring adalah rangkaian huruf tanpa putus, sedangkan subsekuens mempertahankan urutannya tetapi boleh memiliki jeda. Untuk hammer dan harmed, substring umum terpanjang memiliki panjang 2 dan subsekuens umum terpanjang memiliki panjang 4 (hame). Dalam tabel, ketidakcocokan mereset sel substring menjadi 0, tetapi membuat sel subsekuens menyalin nilai tetangganya yang lebih besar.

Apa kompleksitas waktu untuk substring umum terpanjang?

Solusi pemrograman dinamis membutuhkan waktu O(n × m), dan memori O(m) dengan satu baris. Memperluas dari setiap pasangan titik awal membutuhkan O(n × m × min(n, m)) dalam kasus terburuk. Automaton sufiks mencapai sekitar O(n + m), dengan biaya program yang jauh lebih panjang.

Bagaimana cara mengembalikan substring terpanjang yang sama?

Setiap kali sebuah sel memiliki nilai lebih besar daripada best, catat juga posisi i di s1 tempat blok tersebut berakhir. Pada akhirnya, substring tersebut adalah huruf-huruf best dari s1 yang berakhir di posisi itu. Perbandingan lebih besar yang ketat membuat blok terpanjang pertama yang ditemukan di s1 tetap dipilih.

def longestCommonSubstring(s1, s2):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s1 = "clockwork"
s2 = "workshop"

Output yang diharapkan

Longest Common Substring

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Perluas dari setiap pasangan posisi awal

Tabel panjang blok yang berakhir pada setiap pasangan

Satu baris, diperbarui dari kanan ke kiri

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa