给定一个字符串字典D和一个输入字符串S。我试图从D中找到某个字符串p ，它是S的前缀。
对于无序字典，最快的方法似乎是为D构建一个 trie并与S的初始字符一起遍历该 trie 。由于D中的字符串是无序的，因此这里最自然的搜索算法将是找到最长前缀p的算法。
但是，我需要为D中的字符串保留一个特殊的输入顺序。例如，对于D = [ bar, foo, foobar] 和S = foobariously，上述搜索将产生p = foobar，因为它是最长的前缀。但相反，我想得到p = foo，因为foo在输入列表中较早出现。
这种前缀搜索最快的算法是什么？我认为基本方法仍然涉及 trie，但我不知道如何将原始排序集成到其中。