Given a dictionary of strings D and an input string S. I'm trying to find a certain string p from D that is a prefix of S.
For an unordered dictionary the fastest way seems to be building a trie for D and traversing the trie along with the initial characters of S. As the strings in D are unordered, the most natural search algorithm here would be the one that finds the longest prefix p.
However, I need to preserve a special input order for the strings in D. For example, for D = [bar, foo, foobar] and S = foobariously, the above search would yield p = foobar, as it is the longest prefix. But instead I would like to get p = foo, because foo occurs earlier in the input list.
What is the fastest algorithm for that kind of prefix search? I presume that the basic approach still involves a trie, but I don't know how to integrate the original ordering into it.
Just build a trie, but when adding an element, if you find one already there on the way, drop this because that one is better.
That is, when trying to add 'foobar' you'd traverse the trie to 'foo' and realize that you'll never want 'foobar' so drop it.