java - 找到最长的重复字符部分

Question

想象一个像这样的字符串:

#*****~~~~~~****************~~~~~~~~~************ ******************#

我正在寻找一种优雅的方法来查找包含特定字符的最长连续部分的索引。假设我们正在搜索 * 字符，那么我希望该方法返回 * 最后一个长部分的开始和结束索引。

我正在寻找一种优雅的方式，我知道我可以通过检查类似的内容来暴力破解

indexOf(*)
lastIndexOf(*)
//Check if in between the indices is something else if so, remember length start from new 
//substring and repeat until lastIndex reached
//Return saved indices

这真是丑陋的蛮力 - 还有更优雅的方法吗？我考虑了正则表达式组并比较它们的长度。但如何获得索引呢？

Answer 1

基于正则表达式的解决方案

如果您不想硬编码特定字符，例如*，并查找“查找重复字符的最长部分”作为问题的标题指出，那么重复字符部分的正确正则表达式将是:

"(.)\\1*"

其中 (.) 是由单个字符组成的组，\\1 是 backreference that 指的是该组。 * 是贪婪的 quantifier ，这意味着主导反向引用可以重复零次或多次。

最后，"(.)\\1*" 捕获后续相同字符的序列。

现在要使用它，我们需要将正则表达式编译为Pattern。此操作有成本，因此如果多次使用正则表达式，则声明一个常量是明智的:

public static final Pattern REPEATED_CHARACTER_SECTION = 
    Pattern.compile("(.)\\1*");

利用现代 Java 的特性，只需一行代码就可以找到与上述模式匹配的最长序列。

从 Java 9 开始，我们有了方法 Matcher.results()返回 MatchResult 的流对象，描述匹配组。

MatchResult.start() MatchResult.end()公开访问组的开始和结束索引的方式。要提取组本身，我们需要调用 MatchResult.group() .

实现的样子:

public static void printLongestRepeatedSection(String str) {
    
    String longestSection = REPEATED_CHARACTER_SECTION.matcher(str).results() // Stream<MatchResult>
        .map(MatchResult::group)                                              // Stream<String>
        .max(Comparator.comparingInt(String::length))                         // find the longest string in the stream
        .orElse(""); // or orElseThrow() if you don't want to allow an empty string to be received as an input
    
    System.out.println("Longest section:\t" + longestSection);
}

main()

public static void printLongestRepeatedSection(String str) {

    MatchResult longestSection = REPEATED_CHARACTER_SECTION.matcher(str).results() // Stream<MatchResult>
        .max(Comparator.comparingInt(m -> m.group().length()))                     // find the longest string in the stream
        .orElseThrow(); // would throw an exception is an empty string was received as an input

    System.out.println("Section start:   " + longestSection.start());
    System.out.println("Section end:     " + longestSection.end());
    System.out.println("Longest section: " + longestSection.group());
}

输出:

Section start:   34
Section end:     61
Longest section: ***************************

链接:

• ^{官方教程Lambda expressions和 Stream API由Oracle提供}

• ^{关于 Regular expressions 的快速教程}

简单且高性能的迭代解决方案

您可以在不使用正则表达式的情况下通过手动迭代给定字符串的索引并检查前一个字符是否与当前字符匹配来完成此操作。

您只需要维护几个变量来表示之前遇到的最长部分的开始和结束，以及一个变量来存储当前正在检查的部分的起始索引。

这就是它的实现方式:

public static void printLongestRepeatedSection(String str) {
    if (str.isEmpty()) throw new IllegalArgumentException();

    int maxStart = 0;
    int maxEnd = 1;
    
    int curStart = 0;

    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) != str.charAt(i - 1)) {   // current and previous characters are not equal
            if (maxEnd - maxStart < i - curStart) { // current repeated section is longer then the maximum section discovered previously
                maxStart = curStart;
                maxEnd = i;
            }
            curStart = i;
        }
    }
    
    if (str.length() - curStart > maxEnd - maxStart) { // checking the very last section
        maxStart = curStart;
        maxEnd = str.length();
    }

    System.out.println("Section start: " + maxStart);
    System.out.println("Section end:   " + maxEnd);
    System.out.println("Section:   " + str.substring(maxStart,  maxEnd));
}

main()

public static void main(String[] args) {
    String source = "#*****~~~~~~**************~~~~~~~~***************************#";
    
    printLongestRepeatedSection(source);
}

输出:

Section start: 34
Section end:   61
Section:   ***************************