c - 文字列のブース アルゴリズム

Question

Booth Algorithmを使用して SPOJ でこの問題をO(n) 時間で解決しようとしましたが、試したすべてのテスト ケースで機能しましたが失敗しました。 それから私はO（n ^ 2）時間でブルートフォースの方法でやった、それはうまくいった. 両方のケースのコードを添付しました。どこで間違ったのか教えてください。それとも、ブースアルゴリズムはこの問題に対する正しいアプローチですか?

辞書編集的に最小の文字列の最小回転を見つけることは問題ではありません

最初のアプローチの場合、ブースアルゴリズム: http://ideone.com/J5gl5
2番目のアプローチの場合、ブルートフォース: http://ideone.com/ofTeA

Answer 1

たとえば、アルゴリズムは文字列「ABAED」に対して間違った答えを返します。

アルゴリズムは 7 を返します (これは文字列よりも長いですが!)。

正解は0です。

(このバグは、アルゴリズムの説明を見つけた場所にも存在する可能性があることに注意してください!ウィキペディアの記事の履歴/ディスカッションを見ると、バグを修正する多くの編集があります - どちらも元の論文のバグを修正すると主張しており、バグフィックスでバグを修正するには...）

次のように置き換えると、はるかにうまく機能するようです。

if( lst[i] < lst[ans+i+1] )

と

if( lst[j] < lst[ans+i+1] )