Cómo usar el hash rodante y la búsqueda binaria para encontrar la subcadena común más larga

Ya hay algunas buenas respuestas a este hilo. También estoy tratando de dar uno.

Déjenos asumir que usted sabe sobre el hash rodante Si no lo hace, verifique la respuesta de Pawan Bhadauria en este hilo ¿Qué es un hash rodante y cuándo es útil?

Ahora que conoce el hash rodante, podemos comenzar ahora.

Para implementar la búsqueda binaria a cualquier problema, debemos verificar todas las x en S, p (x) => p (y) para todas las y> x.

El punto importante que nos permite usar BS en el problema es que si las cadenas dadas tienen una subcadena común de longitud n, también tienen al menos una subcadena común de cualquier longitud m n.

Entonces, aquí x debe estar en el rango (0, min (| s1 |, | s2 |)) (ambos incluidos). Ahora, para cada x podemos comprobar si existe o no una subcadena común de longitud x. Si existe una subcadena de longitud x, entonces no tenemos que verificar longitudes menores que x o viceversa.

Pseudocódigo para la BS

l = 0, r = min (s1.length (), s2.length ())
mientras que (l <= r) {
mid = l + (rl) / 2
if (p (s1, s2, mid)) // p (s1, s2, len) comprueba la subcadena común
l = medio + 1
más
r = medio – 1
}
volver l-1

Ahora para encontrar es cualquier subcadena común de longitud x existe o no. Para facilitar nuestra salida, tenemos hash rodante.

Para s1, tenemos que encontrar todos los hashes posibles de todas las subcadenas de longitud x y almacenarlos en la tabla hash (he usado stl map para este propósito, puede usar stl set también o cualquier ds de su elección). A continuación, para s2, necesitamos calcular los valores hash de todas las subcadenas de longitud x y comparamos cada valor hash con los valores existentes en la tabla hash si se encuentra una coincidencia, devuelve verdadero. Si no se encuentran coincidencias, se devuelve falso.

Pseudocódigo para Rolling Hash

p (s1, s2, x) {// s1: cadena 1 s2: cadena 2 x: longitud de la subcadena
// Para encontrar hash estoy usando B como primo.
// calcular hash (0) = hash (s1 [0… x-1]) s1 [0] + s1 [1] * B +….
// + s1 [x-1] * pow (B, x-1)
// Para calcular todos los otros hashes, usa esta ecuación
// hash (i) = hash (s1 [i… i + x-1]) = (hash (i-1) – s [i-1]) / B
// + s1 [i + x-1] * pow (B, x-1)
// ahora almacena todos los hashes en la tabla hash
// calcula de manera similar todos los hashes para la cadena 2 y los compara
// con hashes existentes
if (coincidencia encontrada)
volver verdadero
más
falso retorno
}

La complejidad general será log (n) * (nlog (n)).

Gracias Rushal por A2A.

La subcadena común más larga (LCS) de dos cadenas de entrada es una subcadena común (en ambas) de longitud máxima. Podemos relajar las restricciones para generalizar el problema: encontrar una subcadena común de longitud. Entonces podemos usar la búsqueda binaria para encontrar el máximo. Esto lleva tiempo siempre que resolver el problema relajado requiera tiempo lineal.

Encontrar una subcadena común se puede resolver con un hash rodante:

1. Calcular valores hash de todas las subcadenas de longitud de y.
2. Si un hash de coincide con un hash de, entonces hemos encontrado una subcadena común de longitud.

El paso 1 usa un hash rodante para lograr un tiempo lineal y para implementar el paso 2, use una tabla hash. Agregue todos los hashes de las subcadenas de longitud a la tabla. Para cada subcadena de longitud de, búsquela en la tabla. Esto lleva el tiempo lineal esperado para una tabla hash lo suficientemente grande.

Primero observe que la longitud de la subcadena común más larga es como máximo la mínima de las dos cadenas de entrada y que la longitud de la subcadena común más corta es al menos cero (las cadenas no tienen caracteres en común).

izquierda = 0
derecha = min (len (s1), len (s2))
Como tiene un algoritmo para verificar si hay una kcs común de longitud k (llame al algoritmo kcs ). Puede llamarlo O (log n) veces para encontrar el máximo k.

while (izquierda <= derecha) {
k = (izquierda + derecha) / 2
if (kcs (s1, s2, k) == verdadero) {
izquierda = k
}
más {
derecha = k
}
}