algorithm - programacion - matrices en c++ ejercicios resueltos
El algoritmo más eficiente para encontrar el primer prefijo-partido de una matriz de cadenas ordenadas? (6)
Entrada:
1) Una gran variedad ordenada de cadena SA;
2) Una cadena de prefijos P;
Salida:
El índice de la primera cadena que coincide con el prefijo de entrada, si lo hay. Si no existe tal coincidencia, la salida será -1.
Ejemplo: SA = {"ab", "abd", "abdf", "abz"} P = "abd" La salida debe ser 1 (índice comenzando desde 0).
¿Cuál es la forma más algorítmica de hacer este tipo de trabajo?
¿Estás en la posición de precalcular todos los prefijos posibles?
Si es así, puede hacerlo, luego use una búsqueda binaria para encontrar el prefijo en la tabla precalculada. Almacene el subíndice al valor deseado con el prefijo.
El núcleo de FreeBSD usa un árbol Radix para su tabla de enrutamiento, debe verificarlo.
Esta es solo una búsqueda de bisección modificada:
- Solo marque tantos caracteres en cada elemento como estén en la cadena de búsqueda; y
- Si encuentra una coincidencia, continúe buscando hacia atrás (ya sea linealmente o mediante búsquedas de bisección adicionales) hasta que encuentre un resultado que no coincida y luego devuelva el índice del último resultado coincidente.
Mi solución actual es, en lugar de encontrar el "prefijo", intentar encontrar un "prefijo virtual".
Por ejemplo, el prefijo es "abd", intente encontrar un prefijo virtual "abc (255)". (255) solo representa el número máximo de caracteres. Después de localizar el "abc (255)". La siguiente palabra debería ser la primera palabra que coincida con "abd", en su caso.
Se puede hacer en tiempo lineal usando un Suffix Tree . La construcción del árbol de sufijo requiere tiempo lineal.
Si solo quiere hacer esto una vez, use la búsqueda binaria , si por otro lado necesita hacerlo para muchos prefijos diferentes pero en la misma matriz de cadenas, construir una raíz del árbol puede ser una buena idea, después de que haya construido el árbol cada mirada será muy rápido.