Dengan dua urutan, temukan tumpang tindih maksimal antara akhir satu dan awal lainnya

Saya perlu menemukan kode (pseudo) yang efisien untuk menyelesaikan masalah berikut:

Mengingat dua urutan (tidak selalu berbeda) bilangan bulat (a[1], a[2], ..., a[n])dan (b[1], b[2], ..., b[n]), menemukan maksimum dsehingga a[n-d+1] == b[1], a[n-d+2] == b[2], ..., dan a[n] == b[d].

Ini bukan pekerjaan rumah, saya benar-benar datang dengan ini ketika mencoba untuk mengontrak dua tensor sepanjang dimensi sebanyak mungkin. Saya menduga ada algoritma yang efisien (mungkin O(n)?), Tetapi saya tidak dapat menemukan sesuatu yang tidak O(n^2). The O(n^2)pendekatan akan loop jelas di dkemudian loop batin pada item untuk memeriksa kondisi yang diperlukan sampai memukul maksimal d. Tapi saya curiga ada yang lebih baik dari ini.

Anda dapat memanfaatkan algoritma z , algoritma waktu linear ( O (n) ) yang:

Diberikan string S dengan panjang n, Algoritma Z menghasilkan larik Z di mana Z [i] adalah panjang substring terpanjang mulai dari S [i] yang juga merupakan awalan S

Anda harus menyatukan array Anda ( b + a ) dan menjalankan algoritma pada array yang dihasilkan sampai saya yang pertama sehingga Z [i] + i == m + n .

Misalnya, untuk a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0], gabungannya adalah [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3] yang akan menghasilkan Z [10] = 2 memenuhi Z [i] + i = 12 = m + n .

Untuk O (n) kompleksitas ruang / waktu, triknya adalah mengevaluasi hash untuk setiap urutan. Pertimbangkan array b:

[b1 b2 b3 ... bn]

Dengan menggunakan metode Horner , Anda dapat mengevaluasi semua hash yang mungkin untuk setiap urutan. Pilih nilai dasar B(lebih besar dari nilai apa pun di kedua array Anda):

from b1 to b1 = b1 * B^1
from b1 to b2 = b1 * B^1 + b2 * B^2
from b1 to b3 = b1 * B^1 + b2 * B^2 + b3 * B^3
...
from b1 to bn = b1 * B^1 + b2 * B^2 + b3 * B^3 + ... + bn * B^n

Perhatikan bahwa Anda dapat mengevaluasi setiap urutan dalam waktu O (1), menggunakan hasil dari urutan sebelumnya, maka semua biaya pekerjaan O (n).

Sekarang Anda memiliki sebuah array Hb = [h(b1), h(b2), ... , h(bn)], di mana Hb[i]hash dari b1hingga bi.

Lakukan hal yang sama untuk array a, tetapi dengan sedikit trik:

from an to an   =  (an   * B^1)
from an-1 to an =  (an-1 * B^1) + (an * B^2)
from an-2 to an =  (an-2 * B^1) + (an-1 * B^2) + (an * B^3)
...
from a1 to an   =  (a1   * B^1) + (a2 * B^2)   + (a3 * B^3) + ... + (an * B^n)

Anda harus mencatat bahwa, ketika Anda melangkah dari satu urutan ke urutan lain, Anda mengalikan seluruh urutan sebelumnya dengan B dan menambahkan nilai baru dikalikan dengan B. Misalnya:

from an to an =    (an   * B^1)

for the next sequence, multiply the previous by B: (an * B^1) * B = (an * B^2)
now sum with the new value multiplied by B: (an-1 * B^1) + (an * B^2) 
hence:

from an-1 to an =  (an-1 * B^1) + (an * B^2)

Sekarang Anda memiliki sebuah array Ha = [h(an), h(an-1), ... , h(a1)], di mana Ha[i]hash dari aihingga an.

Sekarang, Anda dapat membandingkan Ha[d] == Hb[d]semua dnilai dari n hingga 1, jika cocok, Anda memiliki jawaban.

PERHATIAN : ini adalah metode hash, nilainya bisa besar dan Anda mungkin harus menggunakan metode eksponensial cepat dan aritmatika modular , yang mungkin (jarang) memberi Anda tabrakan , membuat metode ini tidak sepenuhnya aman. Praktik yang baik adalah memilih basis Bsebagai bilangan prima yang sangat besar (setidaknya lebih besar dari nilai terbesar dalam array Anda). Anda juga harus berhati-hati karena batas angka mungkin melimpah di setiap langkah, jadi Anda harus menggunakan (modulo K) di setiap operasi (di mana Kdapat menjadi prima lebih besar dari B).

Ini berarti bahwa dua urutan berbeda mungkin memiliki hash yang sama, tetapi dua urutan yang sama akan selalu memiliki hash yang sama.

Ini memang bisa dilakukan dalam waktu linier, O (n) , dan O (n) ruang ekstra. Saya akan menganggap array input adalah string karakter, tetapi ini tidak penting.

Sebuah metode naif akan - setelah pencocokan k karakter yang sama - menemukan karakter yang tidak cocok, dan kembali k-1 unit di sebuah , ulang indeks di b , dan kemudian memulai proses pencocokan dari sana. Ini jelas merupakan kasus terburuk O (n²) .

Untuk menghindari proses pengulangan ini, kita dapat mengamati bahwa kembali tidak berguna jika kita belum menemukan karakter b [0] saat memindai karakter k-1 terakhir . Jika kita melakukan menemukan karakter itu, maka mundur ke posisi itu hanya akan berguna, jika dalam k berukuran substring kami memiliki pengulangan periodik.

Misalnya, jika kita melihat substring "abcabc" di suatu tempat di a , dan b adalah "abcabd", dan kami menemukan bahwa karakter terakhir dari b tidak cocok, kita harus mempertimbangkan bahwa pertandingan yang berhasil mungkin dimulai pada "a" yang kedua. di substring, dan kita harus memindahkan indeks saat ini di b kembali sesuai sebelum melanjutkan perbandingan.

Idenya adalah untuk melakukan beberapa preprocessing berdasarkan string b untuk login kembali-referensi dalam b yang berguna untuk memeriksa ketika ada ketidakcocokan. Jadi misalnya, jika b adalah "acaacaacd", kita dapat mengidentifikasi referensi-ulang berbasis-0 ini (letakkan di bawah setiap karakter):

index: 0 1 2 3 4 5 6 7 8
b:     a c a a c a a c d
ref:   0 0 0 1 0 0 1 0 5

Misalnya, jika kita memiliki yang sama dengan "acaacaaca" ketidakcocokan pertama terjadi pada karakter terakhir. Informasi di atas kemudian memberi tahu algoritma untuk kembali dalam b ke indeks 5, karena "acaac" adalah umum. Dan kemudian dengan hanya mengubah indeks saat ini di b kita dapat melanjutkan pencocokan pada indeks saat ini dari a . Dalam contoh ini, pencocokan karakter akhir kemudian berhasil.

Dengan ini kita dapat mengoptimalkan pencarian dan memastikan bahwa indeks dalam sebuah selalu bisa maju ke depan.

Berikut ini adalah implementasi dari gagasan itu dalam JavaScript, menggunakan sintaksis paling dasar dari bahasa itu saja:

function overlapCount(a, b) {
    // Deal with cases where the strings differ in length
    let startA = 0;
    if (a.length > b.length) startA = a.length - b.length;
    let endB = b.length;
    if (a.length < b.length) endB = a.length;
    // Create a back-reference for each index
    //   that should be followed in case of a mismatch.
    //   We only need B to make these references:
    let map = Array(endB);
    let k = 0; // Index that lags behind j
    map[0] = 0;
    for (let j = 1; j < endB; j++) {
        if (b[j] == b[k]) {
            map[j] = map[k]; // skip over the same character (optional optimisation)
        } else {
            map[j] = k;
        }
        while (k > 0 && b[j] != b[k]) k = map[k]; 
        if (b[j] == b[k]) k++;
    }
    // Phase 2: use these references while iterating over A
    k = 0;
    for (let i = startA; i < a.length; i++) {
        while (k > 0 && a[i] != b[k]) k = map[k];
        if (a[i] == b[k]) k++;
    }
    return k;
}

console.log(overlapCount("ababaaaabaabab", "abaababaaz")); // 7

Meskipun ada whileloop bersarang , ini tidak memiliki lebih banyak iterasi total daripada n . Ini karena nilai k secara ketat menurun dalam whiletubuh, dan tidak bisa menjadi negatif. Ini hanya bisa terjadi ketika k++dieksekusi yang berkali-kali memberi ruang yang cukup untuk penurunan tersebut. Jadi semuanya, tidak mungkin ada lebih banyak eksekusi whiletubuh daripada k++eksekusi, dan yang terakhir jelas O (n).

Untuk menyelesaikan, di sini Anda dapat menemukan kode yang sama seperti di atas, tetapi dalam cuplikan interaktif: Anda dapat memasukkan string Anda sendiri dan melihat hasilnya secara interaktif:

function overlapCount(a, b) {
    // Deal with cases where the strings differ in length
    let startA = 0;
    if (a.length > b.length) startA = a.length - b.length;
    let endB = b.length;
    if (a.length < b.length) endB = a.length;
    // Create a back-reference for each index
    //   that should be followed in case of a mismatch.
    //   We only need B to make these references:
    let map = Array(endB);
    let k = 0; // Index that lags behind j
    map[0] = 0;
    for (let j = 1; j < endB; j++) {
        if (b[j] == b[k]) {
            map[j] = map[k]; // skip over the same character (optional optimisation)
        } else {
            map[j] = k;
        }
        while (k > 0 && b[j] != b[k]) k = map[k]; 
        if (b[j] == b[k]) k++;
    }
    // Phase 2: use these references while iterating over A
    k = 0;
    for (let i = startA; i < a.length; i++) {
        while (k > 0 && a[i] != b[k]) k = map[k];
        if (a[i] == b[k]) k++;
    }
    return k;
}

// I/O handling

let [inputA, inputB] = document.querySelectorAll("input");
let output = document.querySelector("pre");

function refresh() {
    let a = inputA.value;
    let b = inputB.value;
    let count = overlapCount(a, b);
    let padding = a.length - count;
    // Apply some HTML formatting to highlight the overlap:
    if (count) {
        a = a.slice(0, -count) + "<b>" + a.slice(-count) + "</b>";
        b = "<b>" + b.slice(0, count) + "</b>" + b.slice(count);
    }
    output.innerHTML = count + " overlapping characters:\n" + 
                         a + "\n" + 
                         " ".repeat(padding) + b;
}

document.addEventListener("input", refresh);
refresh();

body { font-family: monospace }
b { background:yellow }
input { width: 90% }

a: <input value="acacaacaa"><br>
b: <input value="acaacaacd"><br>
<pre></pre>