在一个大集合中查找两个字符串的所有串联

算法1:测试对,而不是单子

n^2 查找(其中 n m * n m 是所有字符串的平均长度>=8个字符,减去7,然后 现在是字符串数(大于等于8个字符)。下面是一个实现:

int minWordLength = 4;
int minPairLength = 8;

Set<String> strings = Stream
   .of(
      "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
      "bear", "hug", "bearhug", "cur", "curlique", "curl",
      "down", "downstream", "stream"
   )
   .filter(s -> s.length() >= minWordLength)
   .collect(ImmutableSet.toImmutableSet());

strings
   .stream()
   .filter(s -> s.length() >= minPairLength)
   .flatMap(s -> IntStream
      .rangeClosed(minWordLength, s.length() - minWordLength)
      .mapToObj(splitIndex -> ImmutableList.of(
         s.substring(0, splitIndex),
         s.substring(splitIndex)
      ))
      .filter(pair ->
          strings.contains(pair.get(0))
          && strings.contains(pair.get(1))
      )
   )
   .map(pair ->
      pair.get(0) + pair.get(1) + " = " + pair.get(0) + " + " + pair.get(1)
   )
   .forEach(System.out::println);

downstream = down + stream

它的平均算法复杂度为 男*女 O(n) . 在最坏的情况下, O(n^2) . 看到了吗 hash table

解释

1. 将所有长度为四个或更多字符的字符串放入一个哈希集中(搜索的平均复杂度为O(1))。我用了番石榴 ImmutableSet 为了方便。随便你用。
2. filter :仅限于长度为八个或八个以上字符的项,表示我们的候选项是由列表中的其他两个单词组成的。
3. flatMap :对于每个候选词,计算所有可能的子词对,确保每个子词至少有4个字符长。因为可以有多个结果,这实际上是一个列表列表,所以将其展平为一个单独的深度列表。
   1. rangeClosed :生成表示要检查的对的第一个字中的字符数的所有整数。
   2. mapToObj :将每个整数与候选字符串结合使用,输出两个项的列表(在生产代码中,您可能需要更清晰的内容,如双属性值类或适当的现有类)。
   3. 滤波器
4. map :稍微把结果整理一下。
5. forEach :输出到控制台。

此算法调整为比列表中的项数短得多的单词。如果列表很短,单词很长,那么切换回合成任务而不是分解任务会更好。考虑到列表的大小是50000个字符串,而且德语单词虽然很长,但不太可能超过50个字符,这是有利于此算法的1:1000因素。

另一方面,如果你有50个平均长度为50000个字符的字符串,那么一个不同的算法会更有效率。

我考虑了一会儿的一个算法是对列表进行排序,因为我知道如果一个字符串代表一对的开头,那么所有可能是它的一对的候选字符串都将按顺序紧跟在它之后,在以该字符串开头的一组项目中。整理我上面的棘手数据,并添加一些混淆( downer, downs, downregulate )我们得到:

a
abc
abcdef
bear
bearhug
cur
curl
curlique
def
down ---------\
downs         |
downer        | not far away now!
downregulate  |
downstream ---/
hug
shine
stream
sun
sunshine

因此,如果保留要检查的所有项目的运行集,我们可以在每个单词的基本恒定时间内找到候选组合,然后直接探测剩余单词的哈希表:

int minWordLength = 4;

Set<String> strings = Stream
   .of(
      "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
      "bear", "hug", "bearhug", "cur", "curlique", "curl",
      "down", "downs", "downer", "downregulate", "downstream", "stream")
   .filter(s -> s.length() >= minWordLength)
   .collect(ImmutableSet.toImmutableSet());

ImmutableList<String> orderedList = strings
   .stream()
   .sorted()
   .collect(ImmutableList.toImmutableList());
List<String> candidates = new ArrayList<>();
List<Map.Entry<String, String>> pairs = new ArrayList<>();

for (String currentString : orderedList) {
   List<String> nextCandidates = new ArrayList<>();
   nextCandidates.add(currentString);
   for (String candidate : candidates) {
      if (currentString.startsWith(candidate)) {
         nextCandidates.add(candidate);
         String remainder = currentString.substring(candidate.length());
         if (remainder.length() >= minWordLength && strings.contains(remainder)) {
            pairs.add(new AbstractMap.SimpleEntry<>(candidate, remainder));
         }
      }
   }
   candidates = nextCandidates;
}
pairs.forEach(System.out::println);

结果:

down=stream

这个算法的复杂度要复杂一些。我想搜索的部分是 平均,有 O(n^2) 最坏的情况。最昂贵的部分可能是排序,这取决于使用的算法和未排序数据的特性。所以用这个加一点盐,但有可能。在我看来,这将比建造一个 Trie 从一个庞大的数据集中,因为你只全面地探测它一次,没有得到任何建设成本摊销。

Map.Entry 抱着那对。你怎么做完全是武断的。定制 Pair 类或使用一些现有的Java类就可以了。

你可以改进 Erik’s answer 通过避开大部分潜艇- String 创建使用 CharBuffer 视图并改变其位置和限制:

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将控制操作。除非你进入一个完全不同的方向,比如使用内存映射和重构这个操作 ByteBuffer s。

以第一个字符串作为前缀,第二个字符串作为后缀。 你仔细检查每根绳子。如果字符串以第一个字符串开头,则检查它是否以第二个字符串结尾。一直走到最后。为了在检查字母本身是否相同之前节省一些时间,您可以进行长度检查。 这几乎是你做的,但这个额外的长度检查,你可能可以削减一些。至少这是我的看法。

不确定这是否比你的解决方案好,但我认为值得一试。

构建二 Tries ,一个按正常顺序排列,另一个按倒序排列。

向前走 Trie 从深处 4 .

我贴了一张 特里亚 在这里执行过去 https://stackoverflow.com/a/9320920/823393 .