Tengo un gran conjunto de URL y quiero implementar un autocompletado. No me gusta la complejidad del enfoque ingenuo, ya que es lineal con el tamaño del conjunto:

for(String url: urls) if(url.startsWith(input) {doSomething();}

Ahora sé que en un conjunto de hash, la función "contiene ()" funciona en "O (1)" pero no hay "contienePrefijo ()". ¿Hay una manera simple sin usar una gran biblioteca como Lucene o codificarla yo mismo? No tendría ningún problema para hacerlo, pero parece excesivo para un problema tan simple, así que quiero saber si hay una solución simple existente: -)

De mis clases de ciencias de la computación recuerdo un árbol que consta de fragmentos de cadena pero olvido cómo se llamaba. Funcionó así:

[car, care, carrot,carrotville]->

car
|
-/
-e
-rrot
  |
  ----ville

P.S .: ¿Cómo llamo a los métodos que devuelven todas las cadenas de las cuales es prefijo? Como si a es el prefijo de b, ¿qué es b para a?