Find the longest repeating substring with a length between x and y

Question

Given the line: "blablafblafbla" and 2 limits: x = 3, y = 5 I want to find the longest repeating substring that has a length between x and y. If there are a lot of them, then the first In my example it will be "blaf" A few questions : 1. Is it easier to use a regular expression? 2. I know how to find the longest substring, but where do I need to set the conditions for it to be between x and y?

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

Answer 1

The code you provide is an extremely inefficient way to solve the problem. I would implement the solution using Rabin-Karp or some other hash algorithm that will allow you to solve your problem with O((yx) * L) complexity.

You cannot use regular expressions here - they are designed to solve different problems.

Regarding the question of how to use your solution to find the longest substring with a length between x and y , just change the loop over j to only consider values ​​that are in the interval [x, y] . Here is how you can do it.

 for (int j = Math.max(longest.length() + 1, x) ; j * 2 < text.length() - i && j < y; j++) 

EDIT: to find the longest substring, undo the for loop:

 for (int j = Math.min((text.length() - i -1)/2, y) ; j > longest.length() && j >=x; j--) 

Answer 2

 public static int commonPrefix (String string, int x, int y) { int l = string.length (); int n = 0; int oy = y; while (x < oy && y < l && string.charAt (x) == string.charAt (y)) { n++; x++; y++; } return n; } public static String longestRepeatingSubstring ( String string, int minLength, int maxLength) { String found = null; int l = string.length (); int fl = minLength; for (int x = 0; x < l - fl * 2; x++) for (int y = x + 1; y < l - fl; y++) { int n = commonPrefix(string, x, y); if (n >= maxLength) return string.substring(x, x + maxLength); if (n > fl) { found = string.substring (x, x + n); fl = n; } } return found; } public static void main(String[] args) { System.out.println (longestRepeatingSubstring ("blablafblafblafblaf", 3, 5)); } 

Answer 3

Here is a clumsy regex implementation:

 //import java.util.regex.*; public static String longestRepeatingSubstring (String string, int min, int max) { for (int i=max; i>=min; i--){ for (int j=0; j<string.length()-i+1; j++){ String substr = string.substring(j,j+i); Pattern pattern = Pattern.compile(substr); Matcher matcher = pattern.matcher(string); int count = 0; while (matcher.find()) count++; if (count > 1) return substr; } } return null; } public static void main(String[] args) { System.out.println (longestRepeatingSubstring ("blablafblafbla", 3, 5)); } 

Answer 4

  public static int getCount(String string , String subString){ int count = 0; int fromIndex = 0; do{ if(string.indexOf(subString, fromIndex) != -1){ count++; fromIndex = string.indexOf(subString, fromIndex); } }while(fromIndex == string.length()-1); return count; } public static String longestRepeatingSubstring (int min,int max , String string){ Vector substrs = new Vector(); Vector substrs_length = new Vector(); for (int i=min; i<=max; i++){ for (int j=0; j<string.length()-i+1; j++){ String substr=string.substring(j, i+j); System.out.println(substr); if (substrs.indexOf(substr) == -1){ int count =getCount(string, substr); if (count != 0) { substrs.addElement(substr); substrs_length.addElement(count); } } } } int maxLength = 0; int index = -1; for(int i = 0 ; i < substrs_length.size() ; i++){ int length = (int) substrs_length.elementAt(i); if(length > maxLength){ maxLength = length; index = i; } } return (String) substrs.elementAt(index); } public static void main(String [] arg){ System.out.print(longestRepeatingSubstring(3, 5, "blablafblafbla")); }