[T2] Duda rolling hash parte 1

[balliende]

Hola. Estoy complicada con como funciona el rolling hash en la parte 1. De la forma que lo estoy haciendo, el código se demora mucho en correr, y no estoy segura de que si cumplo la complejidad pedida. ¿Me podrían explicar como formar una tabla de hash, utilizando el rolling hash, y como calcular el hash de la cadena a buscar, siendo que se necesita el hash de la cadena anterior?
Muchas gracias.

[benjavicente]

Hola. Estoy complicada con como funciona el rolling hash en la parte 1. De la forma que lo estoy haciendo, el código se demora mucho en correr, y no estoy segura de que si cumplo la complejidad pedida.

Por lo que hemos visto, solo aplicar hash llega un poco bajo de los 10s en los tests más grandes. Esto es debido a que a pesar de que llegan a la complejidad pedida de $O(N)$ por cada $K$ búsqueda, hay un $c$ constante que se repite innecesariamente en cada iteración. Si se elimina (que no es un cambio grande), el tiempo suele reducirse en al menos la mitad.

¿Me podrían explicar como formar una tabla de hash, utilizando el rolling hash?

No es necesario una tabla de hash u algo complejo para que corra rápido (menos de 5s el hard-3). El hash en este caso tiene otra utilidad, ...

y como calcular el hash de la cadena a buscar, siendo que se necesita el hash de la cadena anterior?

No entendí. Eso es rolling hash (la utilidad que resuelve el problema entregado), que se explica en el documento linkeado en el enunciado y en la cápsula. Feliz con ayudar, pero no entiendo bien que es lo que no queda claro para partir.

[balliende]

En mi código utilizo rolling hash, pero no se si lo estoy implementando de la forma en que debería ser usado, porque mi tiempo en el test hard es muy alto. No puedo mostrar mi código por acá, pero para el hash de la cadena a buscar (no la grande, sino que el pedazo), estoy complicada sobre como calcularlo, para poder compararlo con los hashes de la cadena grande.

[benjavicente]

En mi código utilizo rolling hash, pero no se si lo estoy implementando de la forma en que debería ser usado, porque mi tiempo en el test hard es muy alto.

¿Qué tan alto?

pero para el hash de la cadena a buscar (no la grande, sino que el pedazo), estoy complicada sobre como calcularlo, para poder compararlo con los hashes de la cadena grande.

Para eso, necesitas calcular el hash para un rango de tamaño $M$. Ese cálculo es el mismo que para los primeros $M$ caracteres de la cadena donde se busca de tamaño $N$.

[balliende]

El test hard se demora como 40 segundos. El output es correcto, pero el tiempo es mucho mayor.
¿Hay alguna forma que te pueda mostrar mi código, y como estoy calculando el hash?

[benjavicente]

Como subes el código a esta organización de GitHub, cualquier ayudante puede ver tu código 😅

Tu hash es mejorable, pero no es lo que hace lento to programa.

Como dije inicialmente, el problema suele ser calcular el mismo valor repetidamente dentro de la función de hash (específicamente, en el rolling).

En tu código, hay un par de operaciones que repites muchas veces, que en realidad, solo es necesario calcular 1 o $N$ veces (y no $N\times N$). Ese par de cambios (que son simples) estimo que el tiempo debería bajar al menos en la mitad, y probablemente llegue a pasar 1 o 2 de los test hard.

También, vi que usaste strncpy, cuando en realidad, no es necesario ocuparlo (no se necesita copiar strings porque no los modificas). No usarlo estimo que baje el tiempo en 20% más. En total, mejorar esas 3 cosas podría hacer tu código al menos 70% más rápido.

---

Te recomiendo que vuelvas a revisar esta parte luego de terminar el resto de la tarea y el informe. Vale un poco % respecto al resto de las partes, y alcanzado los mediums, ya se alcanza un 5.5 en la parte.