0

私は新しいJavaで、文字列の最長の部分文字列を見つける割り当てを与えられました。私はオンラインで調査し、この問題にアプローチする良い方法はサフィックスツリーを実装することだと思われます。これを行う方法、または他の解決策があれば教えてください。これは、低レベルの Java 知識で行うことを想定していることに注意してください。

事前に感謝します。

PSテスター文字列は心強いです。 

    /**
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; 
}
4

2 に答える 2

2

コードをデバッグすると、コードが思ったとおりに動作していないことがわかります。私の知る限り、少なくとも 3 つのループが必要であり、最初の文字からのみ開始すると想定することはできません。ここに考えられる解決策の 1 つがあります。

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

版画

abcaab

「安心」のために、それは私の最初の推測ではありrませんでした。s;)

于 2012-11-03T19:30:36.870 に答える
0 
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();
    }
于 2015-02-02T12:41:40.577 に答える