4

文字列 : "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;
}
4

4 に答える 4

2

あなたが提供するコードは、あなたが抱えている問題を解決するための非常に非効率的な方法です。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サイクルを逆にします：

for (int j = Math.min((text.length() - i -1)/2, y) ; j > longest.length() && j >=x; j--)
于 2013-02-08T10:13:49.607 に答える
1

正規表現を使用した不格好な実装を次に示します。

//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));
}
于 2013-02-08T17:10:10.883 に答える
1 
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));
}
于 2013-02-08T10:28:56.480 に答える
0 
    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"));
}
于 2013-02-08T19:36:02.313 に答える