2

私はこの文字列操作の問題を解決しようとしています。そこでは、特定の文字列の最小周期を見つける必要があります。

ストリングは、長さkの別のストリングの1つ以上の繰り返しを連結することによって形成できる場合、周期kを持っていると言われます。

たとえば、文字列「abcabcabcabc」は、文字列「abc」の4回の繰り返しによって形成されるため、期間3があります。また、期間6（「abcabc」の2回の繰り返し）と12（「abcabcabcabc」の1回の繰り返し）があります。これが私のコードです：

public static int getPeriod(String str){
    int len=str.length();   
    boolean flag=false;
    int i;
    
    for (i=0;i<len;i++){
        String s=str.substring(0,i);
        String tmp=str;

        while(tmp.length()>0){
            if(tmp.startsWith(s)){
                tmp=tmp.substring(0,i);
                flag=true;
            }
            
            else {
                flag=false;
                continue;
            }
        }
        
        if (flag==true)
            break;
    }
    
    return i;
 }

s元の文字列を一度に1文字ずつループして、文字列を形成しています。その後、文字列sを何度も連結することで、元の文字列が完全に使い果たされるかどうかを確認しています。

エラー：

このメソッドは常に0を返します。

どうしてこんなことに ？

編集：私のアルゴリズム

入力文字列を考えてみましょうHoHoHo

First step: s=H
        tmp= HoHoHo
        tmp= oHoHo (after substringing tmp)
        'o' isn't the same as s, so we increase i



   Second step:s=Ho
            tmp= HoHoHo
            tmp= HoHo (after substringing tmp)
            tmp= Ho (after substringing tmp)
            tmp= "" (after substringing tmp)
       
Return the value of i, that is 2.
4

4 に答える 4

4

whileループ内のコードは正しくありません。これは、forループの最初の呼び出し中に呼び出されるため、変数i=0への最初の割り当てtmpによって空の文字列に設定され、ループが終了して0になります。フラグの割り当てとcontinueでもelse正しくありません。これを試して：

public static int getPeriod(String str) {
    int len = str.length();
    int i;

    for (i = 1; i <= len/2; i++) {
        String period = str.substring(0, i);
        String tmp = str;
        boolean flag = true;

        while (flag && tmp.length() > 0) {
            if (tmp.startsWith(period)) {
                tmp = tmp.substring(i);
            } else {
                flag = false;
            }
        }

        if (flag == true) {
            return i;
        }
    }
    return 0;
}

長さがゼロの期間をチェックする必要がなく、。より長い期間は存在できないため、forループは開始し1て終了することに注意してください。len/2n/2

于 2012-11-16T10:26:00.537 に答える
2

最初のループ反復では、i == 0であるため、sは ""（空の文字列）であり、最初の反復オーバーwhileループの後のtmpも ""であるため、tmp""になり、すべてのループを終了します。

于 2012-11-16T10:18:13.110 に答える
1

substring（0,0）は ""文字列を返し、tmp.startsWith（ ""）は常にtrueであるため、i=0から開始すると常にtrueが返されます。

まず、iを1から開始する必要があります。また、を置き換える必要がありcontinueます。breakこれcontinueは、続行しますwhile loopが、実行したいのはcontinue、for loopwhileループではなくtheです。

動作するコードのバージョンは次のとおりです。

public static int getPeriod(String str){
    int len=str.length();   
    boolean flag=false;
    int i;

    for (i=1;i<len;i++){
        String s=str.substring(0,i);
        String tmp=str;

        while(tmp.length()>0){
            if(tmp.startsWith(s)){
                tmp=tmp.substring(i);
                flag=true;
            }

            else {
                flag=false;
                break; 
                // Replaced continue with break to exit the while loop and pass 
                // to the next value in the for loop
            }
        }

        if (flag==true)
            break;
    }

    return i;
 }
于 2012-11-16T10:17:26.253 に答える
0

私はこれが古い質問であることを知っています。この問題は、Knuthのプレフィックス関数を使用して線形時間で解決できます。

  public static int prefixFunction(final String needle)
    {
        //This code does not include input validation. Validate the input and return appropriate error message

        int[] pf = new int[needle.length()];
        for (int i = 1; i < needle.length(); i++)
        {
            int j = pf[i - 1];
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) j--;
            if (needle.charAt(i) == needle.charAt(j)) ++j;
            pf[i] = j;
        }
        int n = needle.length(), maxValue = pf[n - 1];
        if(maxValue == 0 || n%(n-maxValue) != 0) return -1; //Not periodic 
        return needle.length() - maxValue;
    }
于 2020-04-02T08:42:14.717 に答える