如何使用 Java Sream 找到最长重复子串？

Question

对于学校作业，我必须实现一种方法，该方法将返回字符串中最长的重复子字符串。但我必须仅使用 Stream API 来完成此操作。

这是我到目前为止所做的：

public static String biggestRedundantSubstring(String s) {
    Stream.Builder<String> stringBuilder = Stream.builder();
    while (!Objects.equals(s, "")) {
        stringBuilder.add(s);
        s = s.substring(1);
    }
    return stringBuilder.build().sorted().reduce("",
            (String biggestRedundantSubstring, String matchingPrefix) ->
                    biggestRedundantSubstring.length() > matchingPrefix.length() ?
                            biggestRedundantSubstring : matchingPrefix,
            (String sub1, String sub2) -> {
                String matchingPrefix = "";
                int limitIndex = Math.max(sub1.length(), sub2.length()) - 1;
                for (int i = 0; i < limitIndex; i++) {
                    if (sub1.charAt(i) == sub2.charAt(i)) {
                        matchingPrefix += sub1.charAt(i);
                    } else {
                        break;
                    }
                }       
                return matchingPrefix;
            });
}

这是main()方法：

public static void main(String[] args) {
    if (args.length != 0) {
        for (String s : args) {
            System.out.println(s + " " + biggestRedundantSubstring(s));
        }
    } else {
        String s = "ababaac";
        System.out.println(s + " " + biggestRedundantSubstring(s));
    }
}

没有参数的情况应该在控制台上打印：

ababaac aba

但它打印的是：

ababaac ababaac

所以我想知道是否可能？我还尝试使用reduce()三个参数，但它也不起作用，我可以使用流外部的变量来跟踪和更改“biggestRedundantSubstring”变量的值，但这有点违背为什么使用流，不是吗？

Answer 1

首先，我们来描述一下整体算法：

• 我们需要生成所有可能的子串。0即，对于从到 的字符串的每个有效索引，str.length() - 1我们必须构造长度从到 的所有子字符串。1str.length() - index

• 然后我们需要检查哪些子串出现多次并选择其中最长的。

要生成所有子字符串，我们需要使用嵌套遍历所有有效索引IntStream（可以使用嵌套循环完成相同的操作for）。当我们拥有所有可能的开始和结束索引时，我们可以将它们转换为子字符串。

然后，要找出这些子字符串中的哪些子字符串出现多次，我们可以使用映射Map<String,Boolean>，其中键是字符串本身，映射到每个键的值将表示它是否重复。我们可以通过使用收集器来做到这一点。 toMap(keyMapper,valueMapper,mergeFunction)

然后当我们需要在辅助映射的条目上创建流时。max()过滤掉重复的条目，并通过使用返回可选对象并期望 aComparator作为参数的操作来选择长度最高的条目。

它可能是这样的：

public static String biggestRedundantSubstring(String str) {
    
    return IntStream.range(0, str.length()) // generating starting indices
        .boxed()
        .flatMap(start -> IntStream.rangeClosed(start + 1, str.length()).mapToObj(end -> str.substring(start,  end))) // generating ending indices and turning each combination of `start` and `end` into a substring
        .collect(Collectors.toMap(   // creating an intermediate map Map<String, Boolean>
            Function.identity(),
            s -> false,              // is repeated substring = false, because element has been encountered for the first time
            (v1, v2) -> true         // substring has been encountered more than once, i.e. is proved to be repeated
        ))
        .entrySet().stream()
        .filter(Map.Entry::getValue) // filtering the repeated substrings
        .max(Map.Entry.comparingByKey(Comparator.comparingInt(String::length))) // returns Optional<Map.Entry<String, Boolean>>
        .map(Map.Entry::getKey)      // returns Optional<String>
        .orElse("");                 // if Optional is empty return an empty string
}

main()

public static void main(String[] args) {
    String s = "ababaac";
    System.out.println(s + " " + biggestRedundantSubstring(s));
}

输出：

ababaac aba