如何使用Java SReam找到最长的重复子弦？

Question

对于学校作业，我必须实现一种方法，该方法将从字符串中返回最长的重复子字符串。但是我必须仅使用流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

所以我想知道是否可能吗？我还尝试使用三个参数使用redy（），但它也不起作用，我可以在流外部使用一个变量来跟踪和更改“ braderedredendansubstring”的值可变，但这违背了为什么使用流，不是吗？

Answer 1

首先，让我们描述总体算法：

• 我们需要生成所有可能的 substring 。 IE对于0到str.length（） - 1的字符串的每个有效索引1 to str.length（） - 索引。

• 然后，我们需要检查以下 substring 不止一次出现并选择最长的子字符串。

要生成所有子字符串，我们需要使用Nested intstream浏览所有有效的索引（可以使用循环的嵌套进行相同的操作）。当我们拥有所有可能的开始和结束索引时，我们可以将它们变成 substrings 。

然后，为了找出这些子字符串不止一次出现，我们可以使用映射map＆lt; string，boolean＆gt;，其中键将是字符串本身和a < em> value 映射到每个键将表示是否重复。我们可以使用 collector “ nofollow noreferrer”> 。

然后，当我们需要在辅助地图的条目上创建流时。滤除重复的条目，然后使用max（）操作选择具有最高长度的条目，该操作返回可选对象并期望比较器作为参数。

这就是外观：

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