CODEWITHSUNDEEP
javastring
Dfsdfsdf Dsfsdfdsf
Dfsdfsdf Dsfsdfdsf

Reputation: 49

How to find the longest repeated substring of given string

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.

Thanks in adavance.

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; 
}

Upvotes: 0

Views: 9104

Answers (2)

Manvendra_0611
Manvendra_0611

Reputation: 146

public static void main(String[] args) {
        String str = "testingString";
        char[] strArr = str.toCharArray();
        StringBuilder bm = new StringBuilder();
        boolean isPresent = false;
        int len = strArr.length;
        int initial =0;
        int dinitial=0;

        HashMap<String, String> hm = new HashMap<String,String>();
        HashMap<String, String> hl = new HashMap<String,String>();
        while(initial<=len-1 && !(dinitial>=len-1)){
            if(!hm.isEmpty()){
                isPresent = hm.containsValue(strArr[initial]+"");
                if(!isPresent){
                    bm.append(strArr[initial]);
                    hm.put(strArr[initial]+"",strArr[initial]+"");
                    if(initial==len-1){
                        System.out.println("Longest substring is::" + bm);
                        break;
                    }
                }
                else if(isPresent){
                    System.out.println("Longest substring is::" + bm);
                    bm.delete(0, bm.length());
                    ++dinitial;
                    initial--;
                    hm.clear();
                }
                initial++;
            }
            else
            {
                    bm.append(strArr[initial]);
                    hm.put(strArr[initial]+"",strArr[initial]+"");
                    initial++;
            }
        }
        hm.clear();
    }

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533482

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;
}

prints

abcaab

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

Upvotes: 2

Related Questions