Mejor forma de implementar el hash de clave parcial

Question

Me presenté para una entrevista en la que me pidieron que escribiera un algoritmo para el hashing de clave parcial, es decir; si se inserta ABCBC en el hash, la búsqueda de cualquiera de las cadenas secundarias debe devolver el valor almacenado. Mi respuesta fue crear una colección de todas las subcadenas posibles de una clave determinada y mantener una asignación entre cada subcadena a su cadena matriz o más. Luego mantenga una BST de la colección de todas las subcadenas. Cada nodo apuntará a una colección de valores reales con los que esa subcadena podría coincidir. Por ej. A, AB, ABC, ABCB, ABCBC, B, BC, BCB, BCBC, C, CB, CBC son posibles subcadenas para esta cadena. Puede haber otras cadenas también como BAB de las cuales AB y B son subcadena. Por lo tanto, dado AB, se asignará a dos cadenas BAB y ABCBC.

¿Hay alguna otra manera más eficiente? Gracias

Answer 1

Almacena cada subcadena en el hash, con una nota para saber si es definitiva, y los posibles caracteres siguientes y anteriores. Almacene los caracteres anteriores para todas las palabras que podrían tener esta subcadena en el centro, y los siguientes caracteres para todas las palabras que tienen esta subcadena como inicio.

Por lo tanto, la entrada para a no necesita tener todas las palabras con a en ella. Pero es bastante fácil construir esa lista si lo desea. Además, durante una inserción, tan pronto como baje de tamaño en subcadenas y descubra que ya tiene la subcadena actual con la continuación actual, puede detenerla.

Suponiendo que tiene muchas palabras con las mismas letras, esto ahorrará algo en espacio e inserciones, a costa de hacer que la lista en realidad sea más lenta. El peor caso sigue siendo O(n*n) para una cadena de letras n.

Para eliminar, puede seguir un procedimiento similar, detener las eliminaciones en cualquier subcadena que tenga otras subcadenas que entren en ella.