Dadas dos secuencias, encuentre la superposición máxima entre el final de una y el comienzo de la otra

Necesito encontrar un código eficiente (pseudo) para resolver el siguiente problema:

Dadas dos secuencias de números enteros (no necesariamente distintos) (a[1], a[2], ..., a[n])y (b[1], b[2], ..., b[n]), encontrar el máximo dtal que a[n-d+1] == b[1], a[n-d+2] == b[2], ..., y a[n] == b[d].

Esto no es tarea, en realidad se me ocurrió cuando intenté contraer dos tensores a lo largo de todas las dimensiones posibles. Sospecho que existe un algoritmo eficiente ( O(n)¿ tal vez ?), Pero no puedo encontrar algo que no lo sea O(n^2). El O(n^2)enfoque sería el bucle obvio dy luego un bucle interno en los elementos para verificar la condición requerida hasta alcanzar el máximo d. Pero sospecho que algo mejor que esto es posible.

Puede utilizar el algoritmo z , un algoritmo de tiempo lineal ( O (n) ) que:

Dada una cadena S de longitud n, el Algoritmo Z produce una matriz Z donde Z [i] es la longitud de la subcadena más larga a partir de S [i], que también es un prefijo de S

Debe concatenar sus matrices ( b + a ) y ejecutar el algoritmo en la matriz construida resultante hasta el primer i tal que Z [i] + i == m + n .

Por ejemplo, para a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0], la concatenación sería [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3] que produciría Z [10] = 2 cumpliendo Z [i] + i = 12 = m + n .

Para O (n) complejidad tiempo / espacio, el truco es evaluar los hashes para cada subsecuencia. Considere la matriz b:

[b1 b2 b3 ... bn]

Usando el método de Horner , puede evaluar todos los hashes posibles para cada subsecuencia. Elija un valor base B(mayor que cualquier valor en ambas matrices):

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

Tenga en cuenta que puede evaluar cada secuencia en el tiempo O (1), utilizando el resultado de la secuencia anterior, por lo tanto, todo el trabajo cuesta O (n).

Ahora tiene una matriz Hb = [h(b1), h(b2), ... , h(bn)], de dónde Hb[i]es el hash desde b1hasta bi.

Haga lo mismo para la matriz a, pero con un pequeño truco:

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)

Debe tener en cuenta que, cuando pasa de una secuencia a otra, multiplica toda la secuencia anterior por B y agrega el nuevo valor multiplicado por B. Por ejemplo:

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)

Ahora tiene una matriz Ha = [h(an), h(an-1), ... , h(a1)], de dónde Ha[i]es el hash desde aihasta an.

Ahora, puede comparar Ha[d] == Hb[d]todos los dvalores de n a 1, si coinciden, tiene su respuesta.

ATENCIÓN : este es un método hash, los valores pueden ser grandes y es posible que deba usar un método de exponenciación rápida y aritmética modular , que puede (apenas) provocar colisiones , lo que hace que este método no sea totalmente seguro. Una buena práctica es elegir una base Bcomo un número primo realmente grande (al menos más grande que el mayor valor en sus matrices). También debe tener cuidado ya que los límites de los números pueden desbordarse en cada paso, por lo que tendrá que usar (módulo K) en cada operación (donde Kpuede ser un primo mayor que B).

Esto significa que dos secuencias diferentes pueden tener el mismo hash, pero dos secuencias iguales siempre tendrán el mismo hash.

De hecho, esto se puede hacer en tiempo lineal, O (n) y O (n) espacio extra. Asumiré que las matrices de entrada son cadenas de caracteres, pero esto no es esencial.

Un método ingenuo podría, después de hacer coincidir k caracteres que son iguales, encontrar un carácter que no coincida y retroceder k-1 unidades en a , restablecer el índice en b , y luego comenzar el proceso de coincidencia desde allí. Esto representa claramente el peor de los casos O (n²) .

Para evitar este proceso de retroceso, podemos observar que retroceder no es útil si no hemos encontrado el carácter b [0] al escanear los últimos caracteres k-1 . Si nos hicimos encontrar que carácter, a continuación, dar marcha atrás a esa posición sólo sería útil, si en ese k sized subcadena tuvimos una repetición periódica.

Por ejemplo, si observamos la subcadena "abcabc" en algún lugar de a , y b es "abcabd", y encontramos que el carácter final de b no coincide, debemos considerar que una coincidencia exitosa podría comenzar en la segunda "a" en la subcadena, y debemos mover nuestro índice actual en b de nuevo en consecuencia antes de continuar la comparación.

La idea es hacer un preprocesamiento basado en la cadena b para registrar las referencias en b que son útiles para verificar si hay una falta de coincidencia. Entonces, por ejemplo, si b es "acaacaacd", podríamos identificar estas referencias inversas basadas en 0 (debajo de cada carácter):

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 ejemplo, si tenemos un igual a "acaacaaca", el primer desajuste ocurre en el personaje final. La información anterior le dice al algoritmo que regrese en b al índice 5, ya que "acaac" es común. Y luego, con solo cambiar el índice actual en b , podemos continuar la coincidencia en el índice actual de a . En este ejemplo, la coincidencia del personaje final tiene éxito.

Con esto podemos optimizar la búsqueda y asegúrese de que el índice en un siempre puede progresar hacia delante.

Aquí hay una implementación de esa idea en JavaScript, utilizando solo la sintaxis más básica de ese lenguaje:

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

Aunque hay whilebucles anidados , estos no tienen más iteraciones en total que n . Esto se debe a que el valor de k disminuye estrictamente en el whilecuerpo y no puede volverse negativo. Esto solo puede suceder cuando k++se ejecutó tantas veces para dar suficiente espacio para tales disminuciones. Así que, en general, no puede haber más ejecuciones del whilecuerpo que k++ejecuciones, y esta última es claramente O (n).

Para completar, aquí puede encontrar el mismo código que el anterior, pero en un fragmento interactivo: puede ingresar sus propias cadenas y ver el resultado de manera interactiva:

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>