辞書的に最小限の弦の回転

文字列の辞書式最小回転を見つけるための単純なアルゴリズムは、連続する回転を繰り返し実行しながら、遭遇した最も辞書式最小の回転を記録していくというものです。文字列の長さがnの場合、このアルゴリズムは最悪の場合O ( n² ⁾の時間で実行されます。

Booth (1980) は効率的なアルゴリズムを提案した。^{[ 3 ]} このアルゴリズムは、Knuth–Morris–Pratt 文字列検索アルゴリズムの修正された前処理関数を使用する。文字列の失敗関数は通常どおり計算されるが、計算中に文字列が回転するため、一部のインデックスは折り返して複数回計算する必要がある。文字列が再び回転することなく失敗関数のすべてのインデックスが正常に計算されると、最小の辞書式回転が見つかり、その開始インデックスが返される。このアルゴリズムの正当性はやや理解しにくいが、実装は容易である。

def least_rotation ( s : str ) -> int : """Boothの辞書式最小文字列回転アルゴリズム。""" n = len ( s ) f = [ - 1 ] * ( 2 * n ) k = 0 for j in range ( 1 , 2 * n ): i = f [ j - k - 1 ] while i != - 1 and s [ j % n ] != s [( k + i + 1 ) % n ]: if s [ j % n ] < s [( k + i + 1 ) % n ]: k = j - i - 1 i = f [ i ] if i == - 1 and s [ j % n ] != s [( k + i + 1 ) % n ]: if s [ j % n ] < s [( k + i + 1 ) % n ] ]: k = j f [ j - k ] = - 1 else : f [ j - k ] = i + 1 return k

興味深いのは、 kの値を変更するコード行をすべて削除すると、元の Knuth-Morris-Pratt 前処理関数になるということです。これは、k (回転を表す) がゼロのままになるためです。 Booth のアルゴリズムは⁠で実行されます。${\displaystyle O(n)}$⁠回数、ここでnは文字列の長さです。アルゴリズムは最大で⁠を実行します。${\displaystyle 3n}$最悪の場合の比較が必要であり、故障関数テーブルを保持するために長さ n の補助メモリが必要です。

Shiloach (1981) ^{[ 4 ]} は、パフォーマンスの点で Booth の結果を改善するアルゴリズムを提案した。長さnの文字列にq個の同等の辞書式最小回転がある場合、その文字列はq個の等しい長さの部分文字列から構成されている必要があることが観察された。${\displaystyle d=n/q}$アルゴリズムに必要なのは⁠だけです${\displaystyle n+d/2}$最悪の場合、比較と一定のスペースが必要になります。

このアルゴリズムは2つのフェーズに分かれています。最初のフェーズは、辞書式最小回転の開始位置として明らかに不適切であるインデックスを除外するクイックシーブです。2番目のフェーズでは、残ったインデックスの中から辞書式最小回転の開始インデックスを見つけます。

デュバル（1983）^{[ 5 ]}は、文字列を構成要素であるリンドン語 に因数分解する効率的なアルゴリズムを提案した。このアルゴリズムは線形時間で実行され、メモリ要件は一定である。