对于包含多个单词的输入字符串——检查它们是否以其他字符串开头的最有效方法是什么？

Question

我需要实现一个 java 方法来获取字符串集和输入字符串，以及 returns 字符串的一个子集，其中包含原始集合中所有以任何单词开头的字符串输入字符串。例如，如果一个字符串是 "Stack Overflow"，而输入是 "Over"，它应该在子集中。但是如果一个字符串是"Stack Overflow"，输入的是“流”，它不应该在子集中。

public Set<String> findMatches (Set<String> names, String input);

由于集合大小很大（1 亿），我需要以最有效的方式执行此操作。到目前为止，我尝试过的三种方法都带来了令人困惑的结果：

用空格拆分每个字符串 space 并获取字符串数组，然后，在数组中的每个项目上 - 调用 String 的 startsWith 方法。
对于每个字符串，检查它是否以输入开头或包含“”+ 输入（空白 space 后跟输入）。
正则表达式。

我测试了这些方法并测量了时间，但令人惊讶的是 - 对于不同的输入值（字符串集和输入字符串） - 我得到了不同的结果（选项 1 在大多数情况下得到了最好的结果，但非常接近其他选项结果）。

那么哪一种最有效呢？还有其他我没有想到的选择吗？

Answer 1

你需要的数据结构是trie.

在这个解释中，我的意思是 t_i 是应该作为单词前缀的小字符串，而 s 是包含许多用空格分隔的单词的大字符串。

只需将所有 t_i 添加到 trie 中。然后遍历s个字符：

如果遇到空格，就去trie的根
如果你遇到一个字母，从当前的 trie 节点转到它的子节点，与这个字母相关联。如果没有路径，则跳过所有字母，直到遇到下一个空格。如果您到达链接到 t_i 之一的节点，请将该字符串添加到答案。

此算法适用于 O(sum(length(t_i)) + length(s))。如果需要我可以写一些代码。

@DudeDoesThings 建议的所有算法和算法都在 O(sum(length(t_i)) * length(s)) 中工作，这要慢得多，尤其是在涉及大输入时。

Answer 2

如果您确实有数百万个字符串并且需要效率，我建议您不要使用拆分或正则表达式。也许您想研究流 API，特别是并行流，如果计算速度是您关心的：

public static void main(String[] args) {
    Set<String> s = Arrays.stream(new String[] {
        "Stack Overflow",
        "Flowover Stack",
        "Overflow Stack",
        "Stackover Flow"
    }).collect(Collectors.toSet());
    System.out.println(findMatches(s, "Over"));
}

public static Set<String> findMatches (Set<String> names, String input) {
    int inputLength = input.length();
    return names.stream().parallel().filter(name -> {
        int offset = 0;
        while (offset >= 0 && offset + inputLength < name.length()) {
            if (name.startsWith(input, offset)) {
                return true;
            }
            offset = name.indexOf(" ", offset);
            if (offset != -1) {
                offset++;
            }
        }
        return false;
    }).collect(Collectors.toSet());
}

对于包含多个单词的输入字符串——检查它们是否以其他字符串开头的最有效方法是什么？

For input string with multiple words - what is the most efficient way to check if any of them start with some other string?

java

string

contains

startswith