Encontrar la ventana más pequeña

Question

Dadas dos matrices A[n] y B[m], ¿cómo puedo encontrar la ventana más pequeña en A que contiene todos los elementos de B.

Estoy tratando de resolver este problema en el momento O (n) pero estoy teniendo problemas para hacerlo. ¿Hay algún algoritmo o procedimiento bien conocido para resolverlo?

Answer 1

CountLet llama a la ventana 'mínima' si no se puede reducir. Es decir, después de aumentar su margen izquierdo o disminuir su borde derecho ya no es una ventana válida (no contiene todos los elementos de B). Hay tres en el ejemplo: [0, 2], [2, 6], [6, 7]

Asumamos decir que usted ya ha encontrado más a la izquierda ventana mínima [izquierda, derecha]. ([0, 2] en su ejemplo) Ahora simplemente lo deslizaremos hacia la derecha.

// count[x] tells how many times number 'x' 
// happens between 'left' and 'right' in 'A' 
while (right < N - 1) { 
    // move right border by 1 
    ++right; 
    if (A[right] is in B) { 
     ++count[A[right]]; 
    } 

    // check if we can move left border now 
    while (count[A[left]] > 1) { 
     --count[A[left]]; 
     ++left; 
    } 

    // check if current window is optimal 
    if (right - left + 1 < currentMin) { 
     currentMin = right - left + 1; 
    } 
} 

Este deslizamiento funciona porque las diferentes ventanas "mínimas" no pueden contenerse entre sí.

Answer 2

Si m > n, A no puede contener todos los elementos de B (y por tanto tenemos una solución O(1)).

De lo contrario:

• crear una tabla de hash elementos de mapeo de B a la secuencia {0..m-1} (esto es O(n) desde).
• Cree una matriz C[m] para contar las ocurrencias de los miembros de B (inicie en 0) en la ventana actual.

• crear una variable z para contar el número de elementos de 0 C (inicializar a m).

• crear variables s y e para indicar el inicio y el final de la ventana actual

• mientras e < n:
  • Si z es distinto de cero, incrementar y actualizar eC y z. O(1)
  • demás consideran esta ventana como una solución posible (es decir, si es el min hasta ahora, almacenarlo), incremente s y actualizar C y z. O(1)

El bucle while puede ser demostrado tener no más de 2n iteraciones. Así que todo es O(n), creo.