Welcome Message

Hi, welcome to my website. This is a place where you can get all the questions, puzzles, algorithms asked in interviews and their solutions. Feel free to contact me if you have any queries / suggestions and please leave your valuable comments.. Thanks for visiting -Pragya.

June 23, 2010

Inefficient O(n^2) Method of finding Largest Recurring Substring in a string

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* @author Pragya Rawal
*/
public class LargestSubstring {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter String : ");
try {
String input = br.readLine();
LargestSubstring str = new LargestSubstring();
String largestSubstr = str.getLargestSubstr(input);
if (largestSubstr != null) {
System.out.println("Largest Recurring substring is : "
+ largestSubstr);
}
} catch (IOException e) {
e.printStackTrace();
}

}

public String getLargestSubstr(String input) {
if (null == input || input.length() == 0) {
System.out.println("Invalid / Empty string ...");
return null;
} else {
int length = input.length();
int subStrLen = 0;
String longestSubStr = "";
String currentStr = "";
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int k = i;
int l = j;
while ((k < length) && (l < length) &&(input.charAt(k) == input.charAt(l)) ) {
currentStr += input.charAt(k);
k++;
l++;
subStrLen++;
}
if (longestSubStr.length() < currentStr.length()) {
longestSubStr = currentStr;
}
currentStr = "";
}

}
return longestSubStr;
}

}
}

1 comment:

harshit said...

the better approach is to use knuth-morris-pratt string searching algorithm with complexity O(n)