如何找到给定字符串的最长重复子字符串 [英] How to find the longest repeated substring of given string

问题描述

我是新的java并且我被赋予了分配以找到字符串的最长子字符串。
我在网上研究，看来解决这个问题的好方法是实现后缀树。
如果您有任何其他解决方案，请告诉我如何做到这一点。请记住，这是假设用低水平的java知识完成的。

I am new java and I was given assignment to find the longest substring of a string. I research online and seems that good way of approaching this problem will be implementing suffix tree. Please let me know how I can do this or if you have any other solutions. keep in mind this is suppose to be done with low level of java knowledge.

谢谢你。

P.S。测试仪字符串让人放心。

P.S. the tester string is reassuring.

    /**
This method will find the longest substring of a given string.
String given here is reassuring. 

 */
public String longestRepeatedSubstring()
{
    String longestRepeatedSubstring = "";
    for (int i = 0; i<text.length(); i++ )
    {
        String one = text.substring(0,i); 

        for(int o = 0; o<text.length();o++)
        {
            Sting two = text.substring(0,o);
            if(one.equals(two))
            {
                longestRepeatedSubstring = one;
            }

        }

    }
    return longestRepeatedSubstring; 
}

推荐答案

如果您调试代码，会看到你的代码没有按你的想法行事。 AFAIK你需要至少三个循环，你不能假设你只会从第一个角色开始。这是一种可能的解决方案。

If you debug your code you will see that you the code isn't doing what you think. AFAIK you need at least three loops and you can't assume you would only start from the first character. Here is one possible solution.

public static void main(String[] args) throws IOException {
    String longest = longestDuplicate("ababcaabcabcaab");
    System.out.println(longest);
}

public static String longestDuplicate(String text) {
    String longest = "";
    for (int i = 0; i < text.length() - 2 * longest.length() * 2; i++) {
        OUTER:
        for (int j = longest.length() + 1; j * 2 < text.length() - i; j++) {
            String find = text.substring(i, i + j);
            for (int k = i + j; k <= text.length() - j; k++) {
                if (text.substring(k, k + j).equals(find)) {
                    longest = find;
                    continue OUTER;
                }
            }
            break;
        }
    }
    return longest;
}

打印

abcaab

安慰打印 r 不是 s 这是我的第一次猜测。 ;）

for "reassuring" it prints r not s which was my first guess. ;)

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