在一个巨大的集合中找到两个字符串的所有连接

Question

给定一组 50k 个字符串，我需要找到所有对(s, t)，例如s，t和s + t都包含在这个集合中。我试过的，还有一个额外的约束：s.length() >= 4 && t.length() >= 4。这使得可以按长度为 4 的前缀和单独的后缀对字符串进行分组。然后对于每个composed长度至少为 8 的字符串，我查找s使用 的前四个字符composed的候选集和t使用其后四个字符的候选集。这有效，但需要查看 30M 候选对(s, t)才能找到 7k 结果。如此高的候选数量来自这样一个事实，即字符串是（主要是德语）词汇量有限的单词，并且单词的开头和结尾通常相同。它仍然比尝试所有 2.5G 对要好得多，但比我希望的要糟糕得多。我需要的由于附加约束可能会被删除并且集合会增长，我正在寻找更好的算法。“失踪”的问题有人抱怨我不问问题。所以缺少的问号在下一个句子的末尾。如何在不使用约束的情况下更有效地完成这项工作？

Answer 1

您可以通过使用视图避免大多数子创建并改变它们的位置和限制来改进Erik 的答案：StringCharBuffer

Set<CharBuffer> strings = Stream.of(

    "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",

    "bear", "hug", "bearhug", "cur", "curlique", "curl",

    "down", "downstream", "stream"

 )

.filter(s -> s.length() >= 4) // < 4 is irrelevant

.map(CharBuffer::wrap)

.collect(Collectors.toSet());

strings

    .stream()

    .filter(s -> s.length() >= 8)

    .map(CharBuffer::wrap)

    .flatMap(cb -> IntStream.rangeClosed(4, cb.length() - 4)

        .filter(i -> strings.contains(cb.clear().position(i))&&strings.contains(cb.flip()))

        .mapToObj(i -> cb.clear()+" = "+cb.limit(i)+" + "+cb.clear().position(i))

    )

    .forEach(System.out::println);

这是相同的算法，因此不会改变时间复杂度，除非您包含隐藏字符数据复制成本，这将是另一个因素（乘以平均字符串长度）。

当然，只有当您使用与打印匹配项不同的终端操作时，差异才会变得显着，因为打印是一项安静且昂贵的操作。同样，当源是大文件上的流时，I/O 将主导操作。除非你进入一个完全不同的方向，比如使用内存映射并重构这个操作来对ByteBuffers进行操作。

Answer 2

一个可能的解决方案可能是这样。您以第一个字符串作为前缀，第二个字符串作为后缀。你遍历每个字符串。如果字符串以第一个字符串开头，则检查它是否以第二个字符串结尾。并一直坚持到最后。为了在检查字母本身是否相同之前节省一些时间，您可以进行长度检查。这几乎是你做的，但通过这个增加的长度检查，你可能可以剪掉一些。至少这是我的看法。