Java Data Structure for string matching
-
01-10-2019 - |
Pergunta
I have a long list of arbitrary strings and I'd like to determine if my given string "ABADCAFE" starts with any of the strings in my list. Is there a library class somewhere that can do this for me reasonably efficiently ?
(I suppose it's much like the state machine built by regex, but I don't think composing a regex is the way to go here - my list is too long)
Solução
What you're looking for is probably a Patricia Tree or Radix Tree: http://en.wikipedia.org/wiki/Radix_tree
Apache Commons Collections and Google Collections Library appear to have the same implementation: http://code.google.com/p/patricia-trie/
Outras dicas
I don't think there is some magic algorithm here that would give you super efficiency; after all, the algorithm has to take a look at each string. Building a finite state machine or a radix tree, or using the foreach -- they're all linear in the number of strings and for this application just quite the same.