查找字符串中最长的重复子字符串？ [英] Find longest repeating substring in string?

问题描述

我遇到了下面看起来很完美的程序。对我来说，它的时间复杂度是nlogn，其中n是字符串的长度。

I came across below program which looks perfect. Per me its time complexity is nlogn where n is the length of String.

n用于存储不同的字符串，nlog用于排序，n用于比较。因此，时间复杂度为nlogn。
空间复杂度是n，用于存储存储的n个子字符串

n for storing different strings,nlog for sorting, n for comparison. So time complexity is nlogn. Space complexity is n for storing the storing n substrings

我的问题是它是否可以进一步优化？

My question is can it be further optimized ?

public class LRS {


    // return the longest common prefix of s and t
    public static String lcp(String s, String t) {
        int n = Math.min(s.length(), t.length());
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != t.charAt(i))
                return s.substring(0, i);
        }
        return s.substring(0, n);
    }


    // return the longest repeated string in s
    public static String lrs(String s) {

        // form the N suffixes
        int n  = s.length();
        String[] suffixes = new String[n];
        for (int i = 0; i < n; i++) {
            suffixes[i] = s.substring(i, n);
        }

        // sort them
       Arrays.sort(suffixes);

        // find longest repeated substring by comparing adjacent sorted suffixes
        String lrs = "";
        for (int i = 0; i < n-1; i++) {
            String x = lcp(suffixes[i], suffixes[i+1]);
            if (x.length() > lrs.length())
                lrs = x;
        }
        return lrs;
    }



    public static void main(String[] args) {
        String s = "MOMOGTGT";
        s = s.replaceAll("\\s+", " ");
        System.out.println("'" + lrs(s) + "'");

    }

}

推荐答案

看看geeksforgeeks中给出的算法，这可能会有所帮助：

Have a look at this algorithm given in geeksforgeeks, this might be helpful:

http://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/

这篇关于查找字符串中最长的重复子字符串？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！