Эффективно получить подмножество строк «startWith» из набора

Question

У меня есть набор большого количества строк, и я хочу создать для него функцию автозапуска.

Предположим, что множество ["foo", "fighter"]

Typing "f" должен возвращать оба значения, и набрав "fo" должен возвращать только "foo".

В настоящее время я просто перебираю результаты и выдаю результаты, позвонив по номеру startsWith, однако это слишком медленно.

Стандарт TreeSet с его функциями подмножества не поможет здесь, поскольку он реализует дерево RB.

Есть ли эффективное решение в Java API или мне нужно создать собственную реализацию Set?

---

Edit: Моя реализация выглядит следующим образом, используя Андрей Naumenkos trie datastructures. Обратите внимание, чтобы увеличить размер массива, если вы хотите использовать расширенные символы ASCII. Если вы используете List вместо Map, вы получите результаты в отсортированном порядке.

public Set<String> getSubset(String s) { 
    result = new HashSet<String>(); 
    getSubset(root, s); 
    return result; 
} 

private void getSubset(TrieNode node, String s) { 
    TrieNode n = node; 
    for (char ch : s.toCharArray()) { 
     if (n.children[ch] != null) { 
      n = n.children[ch]; 
      continue; 
     } 
     return; 
    } 
    getSubsetR(n, s); 
} 

private void getSubsetR(TrieNode node, String s) { 
    for (char ch = 0; ch < node.children.length; ch++) { 
     TrieNode child = node.children[ch]; 
     if (child != null) 
      getSubsetR(child, s + ch); 
    } 
    if (node.leaf) { 
     result.add(s); 
    } 
} 

Answer 1

Что вы ищете является префиксом древовидная структура данных: http://en.wikipedia.org/wiki/Trie

Этот код поможет вам начать работу: https://sites.google.com/site/indy256/algo/trie