字句的に最小限の文字列の回転数を調べるにはどうすればよいですか？

：

 
S = abab, N = 2 
S = abca, N = 1 
S = aaaa, N = 4

私はそれが非常に長く働き、デュバルのアルゴリズムを試してみました。文字列の長さは100000000文字です。

私は、字句的に最小の文字列の回転を望んでいないと思いますが、周期的な文字列のピリオドです。 http://stackoverflow.com/questions/8347812/given-string-s-find-the-shortest-string-t-such-that-tm-s –

ローテーション数はどういう意味ですか？各ローテーションに数字がありますか？回転回数は？むしろ、回転の総数（回転** - **複数**）を望んでいないのですか？ – TMS

** Duvalのアルゴリズムは 'O（1）'メモリ要件で 'O（N）'で動作します。もしこれがあなたにとって遅いと思われるなら、それをあきらめて、速くなることはありません！**プログラムは少なくとも文字列全体を読む必要があります。これは最小時間 'O（N）'を与えます！ – TMS

簡単 - 文字列の最小期間を決定するだけです。最小期間Kで周期的な文字列は、正確にN/K異なる回転のために同じ（したがって辞書的に等しい）文字列を生成するので、辞書編集の最小値が何であれ、N/Kの異なる回転の結果になります。

2014-01-09 17:10:59 Sneftel

私はDuvalのアルゴリズムを試しましたが、非常に長く働いています。文字列の長さは100000000文字です。 – user3164559

なぜデュバルのアルゴリズムが必要ですか？最小置換数の*数*を決めることについては、それらの* any *を見つける必要はありません。 – Sneftel

それでは 'K 'はどうやって見つけられますか？ – user3164559

答えて