Además de la solución O (N ^ 2) mencionada por Raziman, también podemos tener una solución O (N ^ 2 log N) utilizando la búsqueda binaria.
Para encontrar el valor máximo de L, buscamos binariamente en él. Esto funciona porque si existe para L particular i, j tal que M (i, j, L) <= K, entonces obviamente para todo l <L, también existe i, j tal que M (i, j, l ) <= K.
Entonces tenemos
- ¿Cuál es el algoritmo de la suma de los primeros 20 números naturales?
- Cómo calcular la velocidad de un algoritmo
- Dos jugadores juegan el siguiente juego: hay N piedras en la mesa, el jugador puede tomar 1 o 2 piedras (si N mod 3 = 0), 1 o 3 (si N mod 3 = 1) y 1, 2 o 3 ( si N mod 3 = 2). ¿Cómo determino al ganador en el juego?
- ¿Cómo funciona esta recursión?
- Cómo probar si una cadena es una subcadena de otra cadena en C sin ninguna función incorporada
int bajo = 0, alto = l, medio;
while (bajo > 1;
if (resolver (medio)) bajo = medio;
más alto = medio - 1;
}
Ahora la función resolver (x) devolverá verdadero si existimos alguna i, j tal que M (i, j, x) <= K. Esto se puede implementar en el tiempo O (N ^ 2) usando algún cálculo previo.
Podemos mantener un recuento de matriz [i] [j] que nos dirá el número de desajustes entre las cadenas [i-min (i, j) … i] y [j-min (i, j) … j]. Usar esto para cualquier i, j, M (i, j, x) se puede calcular como cuenta [i + x-1] [j + x-1]-cuenta [i-1] [j-1].
Por lo tanto, la función resolver (x) se convierte en algo así:
resolver (int mid) {
para (int i = mid; i <= l; i ++) {
para (int j = mid; j <= l; j ++) {
int tmp = cuenta [i] [j] - cuenta [i-mid] [j-mid];
if (tmp <= K) devuelve verdadero;
}
}
falso retorno;
}
Finalmente, una programación dinámica simple para calcular el recuento [] [] en O (N ^ 2)
l = P.length ();
para (int i = 0; i <l; i ++) {
para (int j = 0; j <l; j ++) {
cuenta [i + 1] [j + 1] = ((P.charAt (i) == Q.charAt (j))? 0: 1) + cuenta [i] [j];
}
}
