Dadas duas seqüências, encontre a sobreposição máxima entre o final de uma e o início da outra

Preciso encontrar um código (pseudo) eficiente para resolver o seguinte problema:

Dadas duas seqüências de números inteiros (não necessariamente distintas) (a[1], a[2], ..., a[n])e (b[1], b[2], ..., b[n]), encontrar a máxima dtal que a[n-d+1] == b[1], a[n-d+2] == b[2], ..., e a[n] == b[d].

Isso não é tarefa de casa, na verdade, eu inventei isso ao tentar contratar dois tensores ao longo de tantas dimensões quanto possível. Suspeito que exista um algoritmo eficiente (talvez O(n)?), Mas não consigo criar algo que não seja O(n^2). A O(n^2)abordagem seria o loop óbvio ativado de, em seguida, um loop interno nos itens para verificar a condição necessária até atingir o máximo d. Mas suspeito que algo melhor que isso seja possível.

Você pode utilizar o algoritmo z , um algoritmo de tempo linear ( O (n) ) que:

Dada uma sequência S de comprimento n, o algoritmo Z produz uma matriz Z em que Z [i] é o comprimento da substring mais longa, começando em S [i], que também é um prefixo de S

Você precisa concatenar suas matrizes ( b + a ) e executar o algoritmo na matriz construída resultante até o primeiro i, de modo que Z [i] + i == m + n .

Por exemplo, para a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0], a concatenação seria [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3] o que daria Z [10] = 2 cumprindo Z [i] + i = 12 = m + n .

Para O (n) complexidade de tempo / espaço, o truque é avaliar os hashes para cada subsequência. Considere a matriz b:

[b1 b2 b3 ... bn]

Usando o método de Horner , você pode avaliar todos os hashes possíveis para cada subsequência. Escolha um valor base B(maior que qualquer valor nas duas matrizes):

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

Observe que você pode avaliar cada sequência no tempo O (1), usando o resultado da sequência anterior, portanto, todos os custos do trabalho O (n).

Agora você tem uma matriz Hb = [h(b1), h(b2), ... , h(bn)], onde Hb[i]está o hash de b1até bi.

Faça o mesmo para a matriz a, mas com um pequeno truque:

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)

Você deve observar que, ao passar de uma sequência para outra, multiplica toda a sequência anterior por B e adiciona o novo valor multiplicado por B. Por exemplo:

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)

Agora você tem uma matriz Ha = [h(an), h(an-1), ... , h(a1)], onde Ha[i]está o hash de aiaté an.

Agora, você pode comparar Ha[d] == Hb[d]para todos os dvalores de n a 1, se eles corresponderem, você tem sua resposta.

ATENÇÃO : este é um método hash, os valores podem ser grandes e você pode ter que usar um método rápido de exponenciação e aritmética modular , que podem (dificilmente) causar colisões , tornando esse método não totalmente seguro. Uma boa prática é escolher uma base Bcomo um número primo realmente grande (pelo menos maior que o maior valor em suas matrizes). Você também deve ter cuidado, pois os limites dos números podem transbordar a cada etapa; portanto, você precisará usar (módulo K) em cada operação (onde Kpode ser um número primo maior que B).

Isso significa que duas seqüências diferentes podem ter o mesmo hash, mas duas seqüências iguais sempre terão o mesmo hash.

Isso pode realmente ser feito em tempo linear, O (n) e O (n) espaço extra. Vou assumir que as matrizes de entrada são cadeias de caracteres, mas isso não é essencial.

Um método ingênuo - após corresponder k caracteres iguais - encontra um caractere que não corresponde e retorna k-1 unidades em a , redefine o índice em b e inicia o processo de correspondência a partir daí. Isso representa claramente o pior caso de O (n²) .

Para evitar esse processo de retorno, podemos observar que voltar atrás não será útil se não encontrarmos o caractere b [0] durante a verificação dos últimos caracteres k-1 . Se nós fez encontrar esse personagem, em seguida, recuar para essa posição só seria útil, se em que k porte substring tivemos uma repetição periódica.

Por exemplo, se olharmos para substring "abcabc" em algum lugar um , e b é "abcabd", e descobrimos que o caráter final da b não corresponder, devemos considerar que um casamento bem-sucedido pode começar na segunda "a" na substring, e devemos mover nosso índice atual em b de volta adequadamente antes de continuar a comparação.

A idéia é, então, realizar um pré-processamento com base na string b para registrar as referências anteriores em b que são úteis para verificar quando há uma incompatibilidade. Por exemplo, se b for "acaacaacd", poderíamos identificar essas referências anteriores baseadas em 0 (coloque abaixo de cada caractere):

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

Por exemplo, se temos um igual a "acaacaaca", a primeira incompatibilidade ocorre no caractere final. As informações acima, então, informam ao algoritmo que retorne em b ao índice 5, pois "acaac" é comum. E então, apenas alterando o índice atual em b , podemos continuar a correspondência no índice atual de a . Neste exemplo, a correspondência do caractere final é bem-sucedida.

Com isso, podemos otimizar a pesquisa e garantir que o índice em um sempre possa avançar.

Aqui está uma implementação dessa ideia em JavaScript, usando apenas a sintaxe mais básica dessa linguagem:

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

Embora existam whileloops aninhados , eles não têm mais iterações no total que n . Isso ocorre porque o valor de k diminui estritamente no whilecorpo e não pode se tornar negativo. Isso só pode acontecer quando k++foi executado tantas vezes para dar espaço suficiente para essas diminuições. Portanto, em suma, não pode haver mais execuções do whilecorpo do que k++execuções, e a última é claramente O (n).

Para concluir, aqui você pode encontrar o mesmo código acima, mas em um snippet interativo: você pode inserir suas próprias strings e ver o resultado interativamente:

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>