查找长度在x和y之间的最长重复子字符串

Question

给定一个字符串：“blablafblafbla”和2个限制：x = 3，y = 5 我想找到长度在x和y之间的最长重复子字符串。有很多，第一个 在我的例子中，这将是“blaf” 几个问题： 1.是否更容易使用正则表达式？ 2.我知道如何找到最长的子字符串，但我必须把它的条件放在x和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

您提供的代码是解决您所遇到问题的极其低效的方法。我会使用Rabin-Karp或其他一些滚动哈希算法来实现解决方案，这将使您能够解决复杂度为O((y-x) * L)的问题。

你不能在这里使用正则表达式 - 它们是为了解决不同的任务。

至于如何使用您的解决方案找到与x和y之间的长度最长的子串你的问题，只需修改遍历j只考虑那些在区间[x, y]值。这是你如何做到的。

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

编辑：找到最长子，扭转了循环：

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

这里是一个笨拙的实现与正则表达式：

//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")); 
}