java - 在 Java 中使用集合中的通配符返回字符串列表的最快方法

Question

我有 100000 个字符串。例如，我想从该集合中获取所有以“JO”开头的字符串。最好的解决方案是什么？

我在想Aho-Corasick but the implementation I have不支持通配符。

Answer 1

如果您想要以序列开头的所有字符串，您可以将所有字符串添加到像 TreeSet 这样的 NavigableSet 中，并获取 subSet(text, text+'\uFFFF') 将为您提供所有条目从 text 开始此查找的时间复杂度为 O(log n)

<小时/>

如果你想要所有的字符串都以一个序列结尾，你可以做类似的事情，只不过你必须反转字符串。在这种情况下，从反向字符串到正向字符串的 TreeMap 将是一个更好的结构。

如果您想要“x*z”，您可以使用第一组进行搜索，并与 map 的值进行并集。

如果你想包含“x”，你可以使用 Navigable> 其中键是从第一个、第二个、第三个字符等开始的每个字符串值是a 设置，因为您可以获得重复项。您可以像开头结构一样进行搜索。