6

次の問題があるとします。

意味 ：

S をアルファベット Σ 上の文字列とします。S'の最小周期は、次のS ようS'な最小の文字列です。

S = (S')^k (S'')、

のS''接頭辞ですS。そのようなものS'が存在しない場合Sは、定期的ではありません。

例: S = abcabcabcabca. Thenabcabcは からのS = abcabc abcabc a期間ですが、最小の期間はabcからS = abc abc abc abc aです。

入力文字列の最小周期を見つけるアルゴリズムを与えるSか、周期的でないと宣言しSます。

ヒント：あなたはそれを行うことができますO(n)...

私の解決策: O(n) で実行される KMP を使用します。

問題の定義 S = (S')^k (S'') により、最短期間 のオートマトンを作成し、その最短期間 を見つける方法を見つければ、完了だと思います。 .

問題はオートマタのFAILの矢をどこに置くか…

どんなアイデアでも大歓迎です、

よろしく

4

5 に答える 5

0

あなたの試みた解決策を理解しているかどうかわかりません。ただし、KMP は便利なサブルーチンです。最小の期間はS、完全に一致した後に KMP が針の列を移動する距離 (つまり ) です。

于 2013-09-04T21:35:50.707 に答える
-1

このソリューションが O(n) で機能するかどうかを確認してください。弦の回転を利用しました。

public static int stringPeriod(String s){

    String s1= s;
    String s2= s1;

    for (int i=1; i <s1.length();i++){
        s2=rotate(s2);
        if(s1.equals(s2)){
            return i;
        }
    }

    return -1;
}

public static String rotate(String s1){

    String  rotS= s1;

    rotS = s1.substring(1)+s1.substring(0,1);

    return rotS;

}

完全なプログラムは、この github リポジトリで入手できます

于 2017-10-07T04:41:18.810 に答える