String Matching.
Dada una cadena y un patrón, su tarea es contar el número de posiciones donde aparece el patrón en la cadena.
Entrada
La primera línea de entrada contiene una cadena de longitud y la segunda línea de entrada contiene un patrón de longitud
. Ambas constan de caracteres de la
a la
.
Salida
Imprime un entero: el número de ocurrencias.
Restricciones
Ejemplo de Entrada
saippuakauppias
ppEjemplo de Salida
2
Comments
Con que algoritmo se puede resolver el ejercicio?
tendrías que leer esto
usa kmp
No sé los demás pero yo lo hice sacando el hashing de las cadenas con doble precisión usando dos hashes se llama polynomial rolling hash function entonces lo que hice fue sacar hashes de cada uno con un módulo y primos diferente para mejorar las colisiones porque parece que hay un caso que no daba por una colisión de ahí para allá es fuerza brutear haber cuáles coinciden.
Yo estoy intentando hacerlo tambien con hash y comprobar si coinciden y me dan TLE 2 casos
No lo estás haciendo bien ,veo que en tu código como que sacas el hash pero luego compruebas brutamente para ver si coinciden ,el punto es ver con la formula el hash de una subcadena contigua de tamaño del segundo string en el primero si coincide con el hash de la segunda completa obviamente y así se hacen las comprobaciones de si coinciden en O(1) y como el total de comprobaciones es primer string.size()-segundo string.size() se hace en O(1e6-1) que sería el peor caso cuando A es de tamaño 1e6 y B de tamaño 1, no entiendo que haces en tu código con el hash.