1) Una gran variedad ordenada de cadena SA;
2) Una cadena de prefijos P;
de salida:
El índice de la primera cadena que coincide con el prefijo de entrada si la hay. Si no existe tal coincidencia, la salida será -1.
Ejemplo: SA = { "ab", "abd", "ABDF", "ABZ"} P = "abd" La salida debe ser 1 (índice a partir de 0).
¿Cuál es la forma más algorítmica de hacer este tipo de trabajo?
Si solo quiere hacer esto una vez, use binary search, si por otro lado necesita hacerlo para muchos prefijos diferentes pero en la misma matriz de cadenas, crear una radix tree puede ser una buena idea, después de que haya construido el árbol cada mirada será muy rápido.
El núcleo de FreeBSD utiliza un Radix tree para su tabla de enrutamiento, debe comprobarlo.
Esto es sólo una búsqueda de bisección modificación:
Se puede hacer en tiempo lineal usando Suffix Tree. La construcción del árbol de sufijo requiere tiempo lineal.
También pudo comparar el prefijo con cada elemento en tiempo lineal. –
Cierto, pero si va a verificar más de un prefijo, esa no es una buena idea. – Brian
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.
¿Está en condiciones 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 mejor tiempo de búsqueda de casos para un árbol raíz es O (n) donde n es el número de caracteres, mientras que la búsqueda binaria toma O (log m) donde m es el tamaño de la lista. No es necesariamente cierto que la búsqueda de radix sea más rápida. –
Arácnido: Esto no es verdad. Incluso en el mejor de los casos (donde hay una coincidencia), la búsqueda binaria es O (n + log m), ya que debe leer todo el prefijo para comprobar si coincide. En el peor de los casos, es O (nlogm). – Brian
@Arácnido: +1 para el comentario de Brian, más O (n) es la búsqueda de CASO PEOR para el árbol de raíz, donde hay una coincidencia y debe leer el prefijo completo. –